Tech Off Post

Single Post Permalink

View Thread: Hierarchical Recursion in T-SQL92
  • User profile image
    Maurits

    This breaks normalization, but it's similar to something I have done in production... and it may work for you.

    In addition to your table of tree nodes:
    CREATE TABLE TreeNode
    (
       NodeID PRIMARY KEY
       ParentNodeID NULL
       Data -- or whatever
    )

    Create a table of top-to-bottom paths:
    CREATE TABLE TreePath
    (
       TopNodeID, -- assuming the roots are at the top
       BottomNodeID, -- assuming the leaves are at the bottom
       Path, -- more on this later
       Length int -- number of edges in the path
    )
    Primary key: (TopNodeID, BottomNodeID)

    Whenever you insert a node into the tree, add the new paths into TreePath.

    Consider this tree:

          1
        / | \
      2  3  4
     /   / \
    5  6  7

    This tree has paths:
    1 -> 2 (length 1)
    1 -> 2 -> 5 (length 2)
    1 -> 3 (length 1)
    1 -> 3 -> 6 (length 2)
    1 -> 3 -> 7 (length 2)
    1 -> 4 (length 1)
    2 -> 5 (length 1)
    3 -> 6 (length 1)
    3 -> 7 (length 1)

    The "Path" field for each path should be the green text shown above.

    You can get an "inorder" traversal of any subtree, starting at any top point, in a single

    SELECT
       BottomNodeID
    FROM
       TreePath
    WHERE
       TopNodeID = @NodeID
    ORDER BY
       Path

    EDIT: Oh, and you can get a list of ancestors (parent, grandparent, great-grandparent...) of any node (going up or down) in a single

    SELECT
       TopNodeID
    FROM
       TreePath
    WHERE
       BottomNodeID = @NodeID
    ORDER BY
       Length -- or Length DESC if you prefer