If you recall a linked list representation, we store each item in a linked list in a structure called Node having two or three fields (depending on whether the list is singly or doubly). A node in a doubly linked list stores a data field, a reference to the previous node and a reference to the next node in the sequence. There are maximum two fields that have a reference to the other nodes.
Like the linked list, we store each item in a tree in a node with data field. The only difference from the linked list representation is that a tree node can have more than 2 references that point to its children nodes. If a node has degree 3, it has 3 reference fields. In general, if a degree of a tree is n, we need n reference fields in each node of the tree. Figure 1 shows the visual representation of a node in a tree.
Figure 2 shows a tree and corresponding representation using the design discussed above.
While this representation is easy to implement and easy to understand, it is only useful for representing a tree that has a small degree e.g. binary tree where a maximum degree is 2. You can see in Figure 2 that most of the reference fields are empty. If a tree has one node with a large degree and other nodes with a small degree, we may waste a lot of memory.
Fortunately, there exists another method of representing a tree that takes only O(n) space. This method is called left-child, right-sibling representation. In this representation, each node has only three fields. One is for storing data and pointers:
- left-child points to the leftmost child of the node
- right-sibling points to the sibling of the immediately to its right.
Figure 3 shows the structure of a node with only three fields.
Figure 3 clearly shows that no matter how many children a node has, it stores only two pointers. Using these scheme, the tree in Figure 2 can be represented as given in Figure 4.
