Offensive Security Researcher & Quantum Cryptography Analyst

Elementary Data Structures: Representing Rooted Trees Explained

Abdul Wahab Junaid
Elementary Data Structures: Representing Rooted Trees

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

How It Works

In the left-child, right-sibling representation, every node x has two fields:

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:

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

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version