# 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

. Since Books & Publications has 3 descendants, its nright is *nright = nleft + (numDescendants * 2) + 1*`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:

```
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
```