hierarchical tree

Posted on 2005-04-19
Last Modified: 2009-08-07
Hi experts,
I have to build a hierarchical tree and am uncertain wich method is the best. I have 2 methods to choose from:

1: Flat Table Model - with a parent Id, rank and indent level
For more info:

2: Modified Preorder Tree Traversal -- with a left and right number
For more info:

Does anyone know what the advantages / disadvantages are of these methods?

Question by:HumanContent
    LVL 19

    Expert Comment

    Personally I'd go for the first method which in my humble opinion is more clear than the other.

    I would  have to say both methods have their strong points and therefor it depends on personal preference which method is 'best'.

    You could get several different answers to this questions and all of them would be accurate.

    LVL 9

    Expert Comment

    I second that emotion. Here's some of my own code that seems to work pretty well:
    LVL 8

    Accepted Solution

    How many nodes you expect to be holding?
    How often will nodes be create, destroyed or moved around in the structure?
    Will the structure always be accessed from the root or will nodes at lower levers be accessed?

    I couldn't see any advantages the the Preorder Tree has over the flat model.   So I thought I would ask what would the set of operations one would want to be able to make on a tree structure.  We would want to be able to acheive these operations without too much complexity balanced with good performance.
    One of the problems with trees and DBs is that they often result in cursors or recursive code initiiating queries over and over again so we would want a structure that help us to aviod that.


    flat model:-

    ID, ParentID, Name, Indentation, Rank  (where rank is a contiguous sequence number through the whole tree)

    The pre-ordered model is:-

    ID, ParentID, Name, LeftID, RightID (see link in question for diagram)

    These are the operations I can think of that we might need and how difficult they might be to achieve.  The list may not be exhaustive and others may better ideas.

    Operations on a tree:-

    1) Read the tree in sequence given a node in that tree (be that a the root node or a descendant somewhere)

    Both methods have a sequential number on which a sort can be achieved.    Both can limit return sets to only children of the current node being queried

    2) Limit reading to direct children only  of as specified node.

    For both models this is very easy using the ParentID field.

    3) Traverse siblings only, forward or backward

    At times you might want to the next sibling of the node (or previous sibling) ignoring any children.  This is very similar to the above since siblings will have the same parentID and previous or following sibilings can be identifed by their sequence number.

    4) Traverse from child back through ancestors to the final root.

    A common operation is discovering a node's ancestors in appropriate sequence (to build a path string for example).  The flat model has trouble with this.  I don't think it can be done with resorting to a cursor (although perhaps there is a better way).  The preordered model can do this since the left hand or right hand sequence id of the original node will always be beween the left hand and right hand sequence ids of it's ancestors also RightID - LeftID  can be used as a sort value to get the ancestors in appropriate order.

    5) Delete and Insert nodes.

    Both models struggle with this since both have sequence numbers covering the whole range of nodes.  Hence on average half the node records will need to be updated when nodes are randomly added and removed.

    6) Testing IsChildOf or IsDescendantOf/IsAncestorOf.

    Due to having a ParentID testing for IsChildOf is easy for both.  For IsDescendantOf/IsAncestorOf in the flat model the rank of the next node that has the same or lower indentation level (in effect finding the equivalent to Preorder's RightID) a descendant will be between this and the current nodes rank.   For the Preorder model it is very easy since any node's sequence ids will be within any of those of it's ancestors.

    7) Number of Children or Descendants.

    For the both models number of children can be acheived with COUNT(*) and the parentID.  Finding number of descendants in the flat model is a little trickier using the same method above to find the effective 'RightID' and then subtracting the current nodes rank.  For the Preordered model number of descendants is simply (Right - Left -1) / 2.

    It would seem then that the preordered approach has the more elegant and effecient solutions to the above set of problems.  I also note that IsDescendantOf and Number of Descendants require some special case handling when the context node is on the right-most extremity of the tree.


    Author Comment

    Great anthony, thanks for the answer, this was excactly what i was looking for. Think i'll go for the pre-ordered model, because of the possibility of Traverse from child back through ancestors to the final root.

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    How to improve team productivity

    Quip adds documents, spreadsheets, and tasklists to your Slack experience
    - Elevate ideas to Quip docs
    - Share Quip docs in Slack
    - Get notified of changes to your docs
    - Available on iOS/Android/Desktop/Web
    - Online/Offline

    Suggested Solutions

    I would like to start this tip/trick by saying Thank You, to all who said that this could not be done, as it forced me to make sure that it could be accomplished. :) To start, I want to make sure everyone understands the importance of utilizing p…
    I was asked about the differences between classic ASP and ASP.NET, so let me put them down here, for reference: Let's make the introductions... Classic ASP was launched by Microsoft in 1998 and dynamically generate web pages upon user interact…
    Illustrator's Shape Builder tool will let you combine shapes visually and interactively. This video shows the Mac version, but the tool works the same way in Windows. To follow along with this video, you can draw your own shapes or download the file…
    In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor ( If you're interested in additional methods for monitoring bandwidt…

    759 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    11 Experts available now in Live!

    Get 1:1 Help Now