When I first started working with trees in code, I realized there isn’t just one “correct” way to represent them in memory. Unlike arrays or linked lists, where the memory layout is basically fixed by definition, a rooted tree can be represented in several genuinely different ways depending on how many children each node might have and what operations I care about most. I want to walk through the standard representations — the binary-tree-style left-child/right-sibling representation in particular — and explain why this specific scheme is so useful for representing trees with an arbitrary, unbounded number of children per node.
This topic matters to me because trees show up everywhere in computing: file systems, parse trees, organizational hierarchies, decision trees, and more. Picking the right representation has a real, measurable impact on how efficiently I can traverse, search, and modify the tree.
History and Background
The representation of rooted trees using pointer-based structures traces back to the earliest days of list-processing languages, particularly Lisp, developed by John McCarthy starting in 1958. Lisp’s fundamental data structure, the cons cell, made it natural to represent arbitrary tree structures using pairs of pointers, and this idea heavily influenced how later computer scientists thought about tree representations in lower-level languages like C.
The specific “left-child, right-sibling” representation — where I give every node just two pointers regardless of how many actual children it has — became a standard technique taught in algorithms courses, notably formalized in Cormen, Leiserson, Rivest, and Stein’s “Introduction to Algorithms” as part of their treatment of elementary data structures. It elegantly solves the problem of representing trees with variable numbers of children using a fixed, binary-tree-like node structure, which simplifies both the code and the memory layout.
Problem Statement
I want to represent a rooted tree in memory — a hierarchical structure where each node (except the root) has exactly one parent, and each node can have zero or more children — in a way that supports efficient traversal (visiting all children of a node, walking up to a parent, and so on). The tricky part is that, unlike a binary tree, a general rooted tree node might have an arbitrary and even variable number of children, and I don’t want to waste memory pre-allocating a fixed-size array of child pointers per node if most nodes only have one or two children while a few have many.
Core Concepts
- Rooted tree: A tree with one designated node called the root, from which every other node is reachable by following parent-to-child edges.
- Parent pointer representation: Each node stores only a pointer to its parent; useful when I only need to walk upward (e.g., for disjoint-set forests), but doesn’t support downward traversal without extra structure.
- Binary tree representation: Each node has exactly two pointers,
leftandright, used directly when the tree is inherently binary (at most two children per node). - Left-child, right-sibling representation: A clever general-purpose scheme for trees with an arbitrary number of children, where each node has exactly two pointers:
left-child, pointing to its first (leftmost) child, andright-sibling, pointing to its next sibling (the next child of the same parent). - k-ary tree representation: Each node has an array (or fixed set) of $k$ child pointers, appropriate when the maximum number of children is known and small.
How It Works
In the left-child, right-sibling representation, every node x has two fields:
x.left-child: points tox‘s leftmost (first) child, orNILifxhas no children.x.right-sibling: points to the next sibling ofx(i.e., the next child ofx‘s own parent), orNILifxis the last child (or an only child).
To find all children of a node, I start at x.left-child and then repeatedly follow right-sibling pointers until I hit NIL, visiting each child of x in turn. To visit a node’s parent, I would need a separate parent pointer if that operation matters for my use case, since the left-child/right-sibling scheme by itself doesn’t provide upward traversal.
This representation essentially reimagines a general tree as a binary tree in disguise: I can think of left-child as playing the role of a binary tree’s “left” pointer, and right-sibling as playing the role of “right.” This isn’t just a cute coincidence — it’s a real, well-known correspondence, sometimes called the “binary tree representation of a general tree” or the “Knuth transform,” and it’s used in practice specifically because it lets tree algorithms reuse binary-tree machinery.
Working Principle
Internally, the left-child/right-sibling scheme works because siblings form a natural singly linked list, threaded through the right-sibling pointers, and each node in that list is itself the head of its own children’s list, threaded through its own left-child/right-sibling chain, recursively. This means the entire tree, no matter how wide or deep, and no matter how many children any individual node has, can be represented using just two pointers per node — exactly the same amount of memory overhead as a plain binary tree node.
Traversal algorithms adapt naturally: a “visit all children” operation becomes “walk the linked list starting at left-child,” and a full tree traversal (like a depth-first traversal visiting every node) recursively applies this same pattern at every level, first descending into left-child, then, after that whole subtree is processed, moving across via right-sibling.
Mathematical Foundation
Space usage. For a tree with $n$ nodes, the left-child/right-sibling representation uses exactly $2n$ pointers (one left-child and one right-sibling per node), plus $n$ units of storage for the node data itself. This gives:
$$ \text{Space} = \Theta(n) $$
regardless of how many children each individual node has, which is asymptotically the same as a plain binary tree representation despite representing trees of arbitrary branching factor.
Comparison to a naive array-of-children representation. If instead I gave each node an array of child pointers sized to the maximum possible branching factor $k$, the space usage would be:
$$ \text{Space} = \Theta(nk) $$
which is strictly worse whenever $k$ is large and most nodes have far fewer than $k$ children — a very common situation in practice (e.g., a file system tree where most directories have only a handful of entries but a few could have thousands).
Traversal time. Visiting all $n$ nodes of the tree via depth-first traversal using the left-child/right-sibling representation takes:
$$ \Theta(n) $$
time, since each node is visited exactly once, and moving between “child” and “sibling” relationships is always an $O(1)$ pointer-following step.
Diagrams
flowchart TD
R[Root] -->|left-child| A[Child 1]
A -->|right-sibling| B[Child 2]
B -->|right-sibling| C[Child 3]
A -->|left-child| D[Grandchild 1.1]
D -->|right-sibling| E[Grandchild 1.2]
C -->|left-child| F[Grandchild 3.1]Pseudocode
Traversal of all children of a node (left-child, right-sibling representation):
VISIT-CHILDREN(x)
child = x.left-child
while child != NIL
VISIT(child)
child = child.right-sibling
Full depth-first traversal of the whole tree:
TREE-WALK(x)
if x != NIL
VISIT(x)
TREE-WALK(x.left-child)
TREE-WALK(x.right-sibling)
Inserting a new child as the leftmost child of a node:
INSERT-FIRST-CHILD(x, z)
z.right-sibling = x.left-child
x.left-child = z
Inserting a new child as the rightmost (last) child of a node:
INSERT-LAST-CHILD(x, z)
z.right-sibling = NIL
if x.left-child == NIL
x.left-child = z
else
current = x.left-child
while current.right-sibling != NIL
current = current.right-sibling
current.right-sibling = z
Step-by-Step Example
Suppose I want to represent this small tree:
A
/ | \
B C D
/ \ |
E F G
Using the left-child/right-sibling representation:
A.left-child = B(A’s first child is B)B.right-sibling = C,C.right-sibling = D,D.right-sibling = NIL(B, C, D are siblings, in that order)B.left-child = E,E.right-sibling = F,F.right-sibling = NIL(E and F are B’s children)C.left-child = NIL(C has no children)D.left-child = G,G.right-sibling = NIL(G is D’s only child)
If I call TREE-WALK(A), the traversal proceeds: visit A, then recurse into A.left-child = B. Visit B, recurse into B.left-child = E. Visit E, E.left-child is NIL so nothing happens there, then move to E.right-sibling = F. Visit F, no children, no further siblings. Back up (implicitly, via the recursive call stack) to finish B‘s subtree, then move to B.right-sibling = C. Visit C, no children, move to C.right-sibling = D. Visit D, recurse into D.left-child = G. Visit G, no children, no siblings. Done.
The full visit order is: A, B, E, F, C, D, G — a valid pre-order traversal of the original tree, achieved entirely through the two-pointers-per-node scheme.
Time Complexity
- Visiting all children of a single node: $O(k)$, where $k$ is the number of children that specific node has, since it’s a simple linked-list walk.
- Full tree traversal (visiting every node once): $\Theta(n)$, where $n$ is the total number of nodes, since each node contributes $O(1)$ work (one visit, one
left-childrecursive call, oneright-siblingrecursive call). - Inserting a new first child: $O(1)$, since it’s just a pointer update at the front of the sibling list.
- Inserting a new last child: $O(k)$ in the naive version shown above, where $k$ is the current number of children, since I need to walk to the end of the sibling list; this can be improved to $O(1)$ by additionally maintaining a
last-childpointer per node. - Finding a specific child by position: $O(k)$ in the worst case, since children are only accessible via sequential traversal of the sibling list, unlike an indexed array representation.
Space Complexity
The left-child/right-sibling representation uses $\Theta(n)$ total space for a tree with $n$ nodes, with exactly two pointers per node regardless of branching factor. This is asymptotically optimal and notably better in constant-factor terms than a fixed-size array-of-children representation whenever the branching factor varies significantly across the tree, since the latter would need $\Theta(nk)$ space where $k$ is the maximum branching factor anywhere in the tree.
Correctness Analysis
The correctness of this representation as a faithful encoding of the original tree structure follows from a simple bijection argument: every parent-child and sibling-order relationship in the original tree maps to exactly one pointer in the left-child/right-sibling structure, and conversely, following left-child and right-sibling pointers from the root always reconstructs the exact same tree shape and sibling ordering that was originally encoded.
For traversal correctness, TREE-WALK is correct by structural induction: the base case is a NIL node, which correctly does nothing. For a non-NIL node x, the recursive definition correctly visits x itself, then correctly (by the inductive hypothesis) traverses the entire subtree rooted at x.left-child (i.e., all of x‘s descendants), and then correctly traverses the rest of x‘s siblings and their descendants via x.right-sibling, covering every node in the tree exactly once.
Advantages
- Uses a fixed, small amount of space per node (just two pointers), regardless of how many children any node actually has, making it memory-efficient for trees with highly variable branching factors.
- Reuses well-understood binary-tree algorithms and intuitions, since the representation is structurally a binary tree in disguise.
- Simple and uniform node structure, which simplifies memory allocation and garbage collection compared to variable-sized array-of-children nodes.
- Naturally supports trees where the branching factor isn’t known in advance or can change dynamically as nodes are added or removed.
Disadvantages
- Accessing a specific child by index (e.g., “give me the 5th child of this node”) requires $O(k)$ traversal of the sibling list, unlike an array-of-children representation which would give $O(1)$ indexed access.
- Doesn’t directly support upward traversal (finding a node’s parent) unless an additional
parentpointer is explicitly maintained, adding a third pointer per node. - Slightly less intuitive to read and debug compared to a straightforward array-of-children representation, especially for programmers new to the technique.
- Some operations that are naturally $O(1)$ with an array of children (like directly modifying the $i$-th child) become $O(k)$ with this representation.
Applications
- Representing file system directory trees, where the number of files/subdirectories per directory varies enormously.
- Parse trees and abstract syntax trees in compilers, where the number of children of a syntax node (e.g., a function call with a variable number of arguments) isn’t fixed.
- XML/HTML DOM tree representations, where each element can have an arbitrary number of child elements.
- Organizational charts and hierarchical data models in general-purpose software, where the “number of direct reports” or similar branching factor varies node to node.
- As a conceptual bridge in algorithms courses, showing how general trees can be handled using the same tools developed for binary trees.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char label;
struct TreeNode *leftChild; /* points to first (leftmost) child */
struct TreeNode *rightSibling; /* points to next sibling */
} TreeNode;
TreeNode* newTreeNode(char label) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->label = label;
node->leftChild = NULL;
node->rightSibling = NULL;
return node;
}
/* Adds 'child' as the new leftmost child of 'parent'. */
void insertFirstChild(TreeNode* parent, TreeNode* child) {
child->rightSibling = parent->leftChild;
parent->leftChild = child;
}
/* Adds 'child' as the new rightmost (last) child of 'parent'. */
void insertLastChild(TreeNode* parent, TreeNode* child) {
child->rightSibling = NULL;
if (parent->leftChild == NULL) {
parent->leftChild = child;
return;
}
TreeNode* current = parent->leftChild;
while (current->rightSibling != NULL) {
current = current->rightSibling;
}
current->rightSibling = child;
}
/* Pre-order traversal: visit node, then its subtree, then its siblings. */
void treeWalk(TreeNode* x, int depth) {
if (x == NULL) return;
for (int i = 0; i < depth; i++) printf(" ");
printf("%c\n", x->label);
treeWalk(x->leftChild, depth + 1);
treeWalk(x->rightSibling, depth);
}
int main(void) {
/* Building the example tree:
A
/ | \
B C D
/ \ |
E F G
*/
TreeNode* A = newTreeNode('A');
TreeNode* B = newTreeNode('B');
TreeNode* C = newTreeNode('C');
TreeNode* D = newTreeNode('D');
TreeNode* E = newTreeNode('E');
TreeNode* F = newTreeNode('F');
TreeNode* G = newTreeNode('G');
insertLastChild(A, B);
insertLastChild(A, C);
insertLastChild(A, D);
insertLastChild(B, E);
insertLastChild(B, F);
insertLastChild(D, G);
printf("Tree structure (indentation shows depth):\n");
treeWalk(A, 0);
return 0;
}
I use insertLastChild throughout the example so that children appear in the same left-to-right order as I originally described the tree, since insertFirstChild would reverse the order of children added one at a time.
Sample Input and Output
Input:
Build tree: A with children B, C, D
B with children E, F
D with child G
Output:
Tree structure (indentation shows depth):
A
B
E
F
C
D
G
This output confirms both the parent-child nesting (shown via indentation) and the correct left-to-right sibling ordering, matching the tree I originally set out to build.
Optimization Techniques
- Maintaining a
last-childpointer per node: ReducesinsertLastChildfrom $O(k)$ to $O(1)$ by avoiding the need to walk the sibling list to find the current last child. - Adding a
parentpointer: If upward traversal is frequently needed, adding a third pointer per node (at the cost of extra memory) turns parent lookups from unsupported into $O(1)$. - Caching child count: If I frequently need to know how many children a node has, storing a
child-countfield avoids repeated $O(k)$ traversal just to count children. - Switching representations based on access pattern: If indexed access to children (e.g., “get the $i$-th child”) is common and branching factor is bounded, a hybrid or array-of-children representation may outperform left-child/right-sibling despite using more memory.
- Memory pooling / arena allocation: For very large trees built and torn down frequently, allocating all nodes from a pre-allocated memory pool rather than individual
malloccalls can meaningfully improve performance in C.
Common Mistakes
- Confusing
left-childwith a binary tree’s “left” in the ordering sense. In this representation,left-childsimply means “first child,” and there’s no notion of “less than” the way there is in a binary search tree — mixing up these two mental models is a common source of confusion for people transitioning from BSTs. - Forgetting to update sibling pointers when removing a node, especially when the removed node is in the middle of a sibling chain — this requires correctly relinking the previous sibling (or the parent’s
left-childpointer, if removing the first child) to skip over the removed node. - Not handling the “no children” (
left-child == NIL) and “no more siblings” (right-sibling == NIL) base cases correctly in recursive traversal code, which can lead to null-pointer dereferences. - Assuming $O(1)$ indexed child access, forgetting that this representation requires an $O(k)$ walk to reach a specific child by position, which can lead to accidentally quadratic code if used carelessly in a loop.
- Memory leaks in C from failing to free every node in the tree (both children and siblings) during cleanup, since a naive
free()on just the root would leak the entire rest of the tree.
Further Reading
- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Chapter 10: “Elementary Data Structures,” MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Knuth, Donald E., The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley: https://www-cs-faculty.stanford.edu/~knuth/taocp.html
- MIT OpenCourseWare, “Introduction to Algorithms” lecture materials on elementary data structures: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- GeeksforGeeks, “Generic Trees (N-ary Trees)”: https://www.geeksforgeeks.org/dsa/generic-treesn-array-trees/
- McCarthy, John, “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I,” Communications of the ACM (1960): https://dl.acm.org/doi/10.1145/367177.367199
