Become Zend Certified

Prepare for the ZCE exam using our quizzes (web or iPad/iPhone). More info...

When you're ready get 7.5% off your exam voucher using voucher CJQNOV23 at the Zend Store

Implementing An N-Level Nested Tree In PHP And PostgreSQL, Part 1

The Nested Tree Model

By introducing a few extra elements of meta-data with each node, we can make the tree run more efficiently by making lookups much quicker and much easier to program.

Note: The nleft and nright values will generally need to be recalculated for most or all nodes when the tree structure changes (e.g. another node is inserted, updated, deleted or moved). If a node is moved its nlevel may also need updating.

nleft, nright and nlevel

The three pieces of meta-data are referred to as the nleft value, the nright value, and the nlevel value.

nlevel is the depth a node is. For instance, in the above tree, General Resources has nlevel 1, all its children (Code Paste, Documentation, Books & Publications, Links) are nlevel 2, and the rest are nlevel 3.

nleft and nright are a little more difficult to explain. Each of these are a unique number (across both fields). In other words, if a node’s nleft value is 3, then 3 won’t appear anywhere else in the nleft or the nright column of other nodes.

A node’s nleft and nright value effectively “wrap” around all its descendant nodes. I’ll try to explain how the number system works, then demonstrate it with an example.

Numbering our example tree

In the above tree, there are 11 nodes. This means the nleft and right values will go from 1 to 22 (since there are two values for each node this is 22 unique values).

We start by giving the root node (General Resources) an nleft value of 1. Since every other node is below the root node, then we give the root node an nright value of 22 (hence it’s “wrapping around” the other numbers). Now we number the rest of the nodes 2 to 21 (since 1 and 22 are used).

The next node is Code Paste. We give this node nleft of 2. This node has no children, so it doesn’t wrap around any other nodes, so we give it nright of 3. From this we can deduce a node without any children always has nright = nleft + 1.

The same applies for Documentation. The next number is 4, so Documentation’s nleft value is 4. This node has no children, so its nright value is 5.

Next is Books & Publications. Its nleft will be 6, however it has children so we can’t just give it an nright of 7. To work out its nright, we count the number of descendants (a node’s children, and their children’s children, and so on). The formula is nright = nleft + (numDescendants * 2) + 1. Since Books & Publications has 3 descendants, its nright is 6 + (3 * 2) + 1 = 13. This formula holds for the previous deduction (where there are no children).

Example tree complete with meta-data

If you continue to number in this fashion, the tree will end up as follows:

Listing 2 listing-2.txt
Title                        ID     PARENT ID     NLEFT     NRIGHT     NLEVEL
General Resources             1          0           1        22          1
   Code Paste                 2          1           2         3          2
   Documentation              3          1           4         5          2
   Books & Publications       4          1           6        13          2
      Apache                  5          4           7         8          3
      PostgreSQL              6          4           9        10          3
      MySQL                   7          4          11        12          3
   Links                      8          1          14        21          2
      Databases               9          8          15        16          3
      Generators             10          8          17        18          3
      Portals                11          8          19        20          3

In This Article