Left-child right-sibling binary tree

^[1]

A way to represent a multiway or k-ary tree is as a binary tree. The left side of node is called a child – a specific node is one of the nodes to which it points, in the next level down on the tree, the next child node is called a sibling – like a human child it has the same parent as the other child.^[2]

6-ary tree represented as a binary tree

Every multi-way or k-ary tree structure studied in computer science admits a representation as a binary tree, which goes by various names including child-sibling representation,^[3] left-child, right-sibling binary tree,^[4] doubly chained tree or filial-heir chain.^[5]

In a binary tree that represents a multi-way tree T, each node corresponds to a node in T and has two pointers: one to the node's first child, and one to its next sibling in T. The children of a node thus form a singly-linked list. To find a node n's k'th child, one needs to traverse this list:

procedure kth-child(n, k):
    child ← n.child
    while k ≠ 0 and child ≠ nil:
        child ← child.next-sibling
        k ← k − 1
    return child  // may return nil

A trie implemented as a doubly chained tree: vertical arrows are child pointers, dashed horizontal arrows are next-sibling pointers. Tries are edge-labeled, and in this representation the edge labels become node labels on the binary nodes.

The process of converting from a k-ary tree to an LC-RS binary tree is sometimes called the Knuth transform.^[6] To form a binary tree from an arbitrary k-ary tree by this method, the root of the original tree is made the root of the binary tree. Then, starting with the root, each node's leftmost child in the original tree is made its left child in the binary tree, and its nearest sibling to the right in the original tree is made its right child in the binary tree.

Doubly chained trees were described by Sussenguth in 1963.^[7]

Processing binary tree to LC-RS binary tree, every node is linked and aligned with the left child, and the next nearest is a sibling. For example, we have a binary tree below:

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

We can re-write it by putting the left child node to one level below its parents and by putting the sibling next to the child at the same level – it will be linear (same line).

                  1          
                 /            
                /             
               /              
              2---3---4       
             /       /       
            5---6   7        
                   /          
                  8---9

We can transform this tree to a binary tree by turning each sibling 45° clockwise.^[8]

               1             
               /              
              2               
             / \              
            5   3             
             \   \            
              6   4           
                 /            
                7             
               /              
              8               
               \             
                9

Use cases

LCRS representation is of two normal criteria:

1) LCRS representation is used much memory.

2) Random access of a node's children is not required.

Case (1) if you need to store the huge multiway tree that contain many data or have a big memory. For example, if you need to store phylogenetic tree, use the LCRS representation might be suitable.

Case (2) arises in specialized data structures in which the tree structure is being used in very specific ways. For example, many types of heap data structures that use multiway trees can be space optimized by using the LCRS representation. The main reason for this is that in heap data structures, the most common operations tend to be

1) Remove the root of a tree and process each of its children, or

2) Join two trees together by making one tree a child of the other.

Operation (1) it is very efficiently. In LCRS representation, it is organized the tree to have a right child because it no have a sibling, so it is easy to remove the root.

Operation (2) it is also efficiently. It is easy to join two trees together.^[9]

References