Left-child right-sibling binary tree

For example, we have a ternary tree below: 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).

[6] 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.

For example, if storing a phylogenetic tree, the LCRS representation might be suitable.

For example, many types of heap data structures that use multi-way trees can be space optimized by using the LCRS representation.

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.

6-ary tree represented as a binary tree
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.