View source for Left-child right-sibling binary tree

[[File:N-ary to binary.svg|thumb|right|250px|6-ary tree represented as a binary tree]]
Every [[multi-way tree|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''',<ref name=FSST>{{cite journal | last1 = Fredman | first1 = Michael L. | author1-link = Michael Fredman | last2 = Sedgewick | first2 = Robert | author2-link = Robert Sedgewick (computer scientist) | last3 = Sleator | first3 = Daniel D. | author3-link = Daniel Sleator | last4 = Tarjan | first4 = Robert E. | author4-link = Robert Tarjan | doi = 10.1007/BF01840439 | issue = 1 | journal = Algorithmica | pages = 111–129 | title = The pairing heap: a new form of self-adjusting heap | url = https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf | volume = 1 | year = 1986}}</ref> '''left-child, right-sibling binary tree''',<ref>{{Introduction to Algorithms|2|pages=214–217}}</ref> '''doubly chained tree''' or '''filial-heir chain'''.<ref>{{DADS|Binary tree representation of trees|binaryTreeRepofTree}}</ref>

In a binary tree that represents a multi-way tree {{mvar|T}}, each node corresponds to a node in {{mvar|T}} and has two [[pointer (computer programming)|pointers]]: one to the node's first child, and one to its next sibling in {{mvar|T}}. The children of a node thus form a [[singly-linked list]]. To find a node {{mvar|n}}'s {{mvar|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''

[[File:Pointer implementation of a trie.svg|thumb|A [[trie]] implemented as a doubly chained tree: vertical arrows are {{mono|child}} pointers, dashed horizontal arrows are {{mono|next-sibling}} pointers. Tries are [[Graph labeling|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 ''[[Donald Knuth|Knuth]] transform''.<ref>Computer Data Structures. John L. Pfaltz.</ref> 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 [[Edward H. Sussenguth]] in 1963.<ref>{{Cite journal | doi = 10.1145/366552.366600| title = Use of tree structures for processing files| journal = [[Communications of the ACM]]| volume = 6| issue = 5| pages = 272–279| date = May 1963| last1 = Sussenguth | first1 = Edward H. | doi-access = free}}</ref>

Processing a k-ary 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 ternary 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{{snd}} 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.<ref>{{Cite web|title = binary tree representation of trees|url = https://xlinux.nist.gov/dads/HTML/binaryTreeRepofTree.html|website = xlinux.nist.gov|accessdate = 2015-11-24}}</ref>

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

==Use cases==
The LCRS representation is more space-efficient than a traditional multiway tree, but comes at the cost that looking up a node's children by index becomes slower. Therefore, the LCRS representation is preferable if

# Memory efficiency is a concern, and/or
# Random access of a node's children is not required.

Case (1) applies when large multi-way trees are necessary, especially when the trees contains a large set of data.   For example, if storing a [[phylogenetic tree]], 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 multi-way trees can be space optimized by using the LCRS representation. (Examples include [[Fibonacci heap]]s, [[pairing heap]]s and [[weak heap]]s.)  The main reason for this is that in heap data structures, the most common operations tend to be

# Remove the root of a tree and process each of its children, or
# Join two trees together by making one tree a child of the other.

Operation (1) it is very efficient. In LCRS representation, it organizes the tree to have a right child because it does not have a sibling, so it is easy to remove the root.

Operation (2) it is also efficient. It is easy to join two trees together.<ref>{{Cite web|title = What is the left-child, right-sibling representation of a tree? Why would you use it?|url = https://stackoverflow.com/questions/14015525/what-is-the-left-child-right-sibling-representation-of-a-tree-why-would-you-u|website = stackoverflow.com|accessdate = 2016-12-12}}</ref>

==References==
{{reflist}}
{{CS-Trees}}

[[Category:Binary trees]]