leftchildrightsibling

Left-child right-sibling (LCRS) is a representation of rooted trees in which each node contains two pointers: one to its left child, and one to its right sibling. In this scheme, any node can have an arbitrary number of children by linking them via a chain of right pointers starting from the left child. The structure effectively stores a multiway tree as a binary tree.

To traverse the children of a node, you start at the left child and follow the right pointers to visit every child in order. A node’s own right pointer links to its next sibling, while a parent’s left pointer points to its first child. Standard tree operations can be adapted: depth-first search becomes a binary-tree traversal with an explicit child traversal step.

Advantages include a uniform storage model compatible with binary-tree algorithms and simple memory management for variable arity trees. The cost is typically extra pointer dereferences and linear time to access deeper siblings; insertions or deletions of a child may require relinking pointers. Space complexity is O(n) for n nodes with two pointers each, comparable to other tree representations when pointer size is considered.

LCRS is also known as the first-child, next-sibling representation and is used in computer science for representing general trees in data structures and in parsing and DOM implementations.