Boo-AI — Master Artificial Intelligence by Building from Scratch

Why Representation Matters

A tree is a mathematical object: a set of nodes with a parent-child relation that has no cycles. That definition tells you what a tree is, but it doesn't tell you how to put one inside a computer. The same abstract tree can live in memory in radically different layouts — some that crush every operation into a single index calculation, some that bloat by a factor of two but let the tree change shape freely, some that store nothing but parent references and still answer ancestor queries efficiently.

Picking the right representation is one of the most consequential decisions in tree-heavy code. The CPU heap-allocator, the file system inode table, the DOM in your browser, the AST your compiler walks, the priority queue inside a Linux scheduler — each picks a different layout because each cares about different operations being cheap. By the end of this section you should be able to look at a workload and pick the layout whose worst case never bites you.

The deeper truth. The abstract tree only constrains the parent-child relation. $O(n)$ different physical encodings can satisfy the same relation. Choosing among them is an engineering decision driven by which operations dominate your workload, not a mathematical one.

What a Tree Must Actually Encode

Forget code for a moment. To fully describe a tree of $n$ nodes you must encode three things:

Identity. Each node has some payload — a key, a value, a record. Without payload the tree has nothing to compute on.
Structure. Which node is whose child. With $n$ nodes there are exactly $n - 1$ parent-child edges in any tree, no more, no less — this is the tree's defining edge count.
Order (sometimes). Whether the children of a node are ordered (left vs. right matters in a binary tree) or unordered (just a set of children, like in a file system directory).

Every representation we're about to study encodes those three things differently. Some merge identity and structure into a single index (array layout). Some split them apart and bolt them together with pointers (linked layout). Some throw away child information and keep only parent information (parent-pointer layout) — and somehow this is enough for huge classes of problems.

Counting the bits

For a labeled tree on

n

nodes, information theory says you need at least

\log_2(n!) + (n-1) \cdot \log_2 n

bits to identify it exactly — the first term names the nodes, the second locates each parent. Real representations spend more bits than this lower bound; the gap is what buys you fast operations.

Representation 1: Implicit Array (Heap Layout)

The most economical layout for a complete binary tree (one with every level full except possibly the last, which fills left to right) puts the nodes in a flat array and uses arithmetic to locate parents and children. No pointers. No structure bookkeeping at all.

The arithmetic

Number nodes $0, 1, 2, \dots, n-1$ in level order — root first, then everything at depth 1, then depth 2, and so on, left to right. With this numbering the relations between parent and children become arithmetic identities:

Left child of $i$ : $2i + 1$
Right child of $i$ : $2i + 2$
Parent of $i$ : $\lfloor (i - 1) / 2 \rfloor$

Why does this work? Level $d$ contains exactly $2^d$ nodes (when full), so the levels start at indices $0, 1, 3, 7, 15, \dots$ — that is, at $2^d - 1$ . Doubling and adding one steps you down one level; integer-dividing and subtracting one steps you up. The arithmetic is just the level structure made explicit.

Some textbooks number from

1

instead of

0

and get the cleaner formulas

2i, 2i+1, \lfloor i/2 \rfloor

. Both work; the 0-indexed form fits C and Python arrays without the wasted slot at index 0.

What it costs and what it buys

Per node we pay just the size of the payload — zero pointer overhead. For a tree with $n = 10^7$ integer keys, that's 40 MB instead of 120 MB for a linked layout (40 MB payload + 80 MB pointers). And because the array is contiguous, sequential access is cache-friendly: walking nodes in level order is a streaming read pattern, the easiest workload for prefetchers to optimize.

The cost: every "empty slot" in the conceptual tree still occupies space. A skinny tree of height $h$ with only $h+1$ nodes still requires a buffer of size $2^{h+1} - 1$ — an exponential blow-up. This layout is therefore reserved for trees you can guarantee are balanced — the canonical example is a binary heap.

Representation 2: Linked Nodes (Pointer Layout)

The textbook representation. Each node lives in its own heap-allocated record holding a payload and pointers to its children. Pointers are $\text{NULL}$ when a child is absent.

📄c

1struct Node {
2    KeyType       data;
3    struct Node  *left;
4    struct Node  *right;
5};

Per-node footprint: $\text{sizeof}(\text{data}) + 2 \cdot \text{sizeof}(\text{pointer})$ . On 64-bit systems that's 16 bytes of pointer overhead per node. In exchange you can represent any binary tree shape — balanced, skinny, gnarled, deeply unbalanced — with no waste and no pre-declared capacity. Insertion and deletion at any position cost $O(1)$ pointer swings.

Why two pointers, not three?

Some implementations add a parent pointer for a third 8 bytes per node. Whether to pay for it depends on access patterns:

Operation	Without parent ptr	With parent ptr
walk root → leaf	O(h)	O(h)
walk leaf → root	O(n) (need to re-search!)	O(h)
delete a node given its address	O(h)	O(1) amortized
per-node memory	16 bytes overhead	24 bytes overhead

Operations like the BST successor function and rotation in red-black trees walk both up and down the tree, so they typically pay for the parent pointer. Pure traversals like printing or size-counting only walk down and don't need it.

Representation 3: Parent-Pointer Array

Now the surprise: we can represent a tree using only the parent relationship, with no child pointers at all. Number the nodes $0, 1, \dots, n-1$ and store an array $\text{parent}[i]$ where each entry is the index of node $i$ 's parent (with the root's parent set to $-1$ by convention).

📄c

1int parent[n];     // parent[i] = index of i's parent, or -1 for root
2KeyType data[n];   // data[i]   = payload of node i

That's the entire representation. Two arrays. Total memory: $n \cdot (\text{sizeof}(\text{int}) + \text{sizeof}(\text{data}))$ .

What can you do with just parent pointers? A surprising amount:

Find any ancestor of a node in $O(h)$ by walking parent links until you hit $-1$ .
Test if two nodes are in the same connected component by walking each to its root and comparing — the entire foundation of union-find (Kruskal's MST, image segmentation, equivalence classes) sits on this.
Compute lowest common ancestor with two parent walks plus a depth array.

What you cannot easily do: ask "list the children of node $i$ " in better than $O(n)$ , because you'd need to scan the entire $\text{parent}$ array looking for entries equal to $i$ . So this layout is for upward queries only. When that's your workload — union-find is the prototypical case — the parent array is unbeatable: dense, branchless inner loop, perfect cache behavior.

A real-world cameo

On every Unix-like system, each process has a single parent process and the kernel stores only the

\text{ppid}

— the parent process id — in the process descriptor, not a list of children. That is a parent-pointer tree. To list a process's children, the kernel scans the process table; to walk to

\text{init}

from any process, it follows

\text{ppid}

links in

O(\text{depth})

Representation 4: Left-Child / Right-Sibling (LCRS)

Trees in real life often aren't binary. A directory has any number of files. A document's DOM tree has paragraphs with arbitrarily many spans inside them. An XML element has unbounded children. The naive approach — storing a vector of child pointers per node — works but uses variable space per node and complicates traversal code.

Left-Child / Right-Sibling encodes any n-ary tree using exactly the same struct layout as a binary tree:

📄c

1struct Node {
2    KeyType      data;
3    struct Node *firstChild;   // leftmost child, or NULL
4    struct Node *nextSibling;  // next child of this node's parent, or NULL
5};

Two pointers, regardless of how many children a node has. To list the children of a node, you follow $\text{firstChild}$ , then chain through $\text{nextSibling}$ until you hit $\text{NULL}$ . It's effectively a linked list of children dangling off each parent.

The marvel: this representation is structurally isomorphic to a binary tree. If you treat $\text{firstChild}$ as "left" and $\text{nextSibling}$ as "right", every algorithm written for binary trees works on n-ary trees encoded this way. You only need one set of code.

LCRS is what your filesystem inode table uses for directory entries on classic Unix filesystems, and what XML / JSON parsers usually emit when they need to support arbitrary branching factors without per-node arrays.

Representation 5: Adjacency List (Graph-Style)

A tree is a special case of a graph (an acyclic, connected one). So every general graph representation also represents trees. The most common is the adjacency list: for each node, store a list of its neighbors.

🐍python

1children = {
2    "A": ["B", "C"],
3    "B": ["D", "E"],
4    "C": ["F", "G"],
5    "D": [], "E": [], "F": [], "G": [],
6}

Children-only adjacency lists work when the tree is rooted and you know which direction edges point. For unrooted trees you store edges in both directions. This format is the natural one when your tree comes out of a graph algorithm (BFS / DFS spanning trees, Prim's tree, Dijkstra's shortest-path tree) and you want to keep using graph-shaped tools on it.

Compared to LCRS, an adjacency list is more flexible (you can store children in any order, append cheaply with a Python list or C++ vector, query $\text{deg}(v)$ in $O(1)$ ) but uses one extra pointer per child for the dynamic-array bookkeeping.

Interactive: Four Views of One Tree

Below is the same 7-node tree shown four different ways. Click any node in the diagram to lock the highlight; the four panels below light up the same logical node in their own layout. Notice how each representation finds the active node through a completely different mechanism — index arithmetic, pointer dereference, parent walk, sibling chain.

Click a node to lock the highlight. Hover changes it temporarily.active node = E (index 4)

1. Array (heap layout)left(i)=2i+1, right(i)=2i+2, parent(i)=(i-1)/2

[0]A

[1]B

[2]C

[3]D

[4]E

[5]F

[6]G

For node E (i=4):

parent index = (4-1)/2 = 1
left child index = 2·4+1 = 9 (out of range → no left child)
right child index = 2·4+2 = 10 (out of range → no right child)

2. Linked nodesstruct { data, *left, *right }

@0x1000Aleft→0x1010right→0x1020

@0x1010Bleft→0x1030right→0x1040

@0x1020Cleft→0x1050right→0x1060

@0x1030Dleft→NULLright→NULL

@0x1040Eleft→NULLright→NULL

@0x1050Fleft→NULLright→NULL

@0x1060Gleft→NULLright→NULL

3. Parent-pointer arrayparent[i] = index of i's parent

[0]−1

[1]0

[2]0

[3]1

[4]1

[5]2

[6]2

From E, walking up: E → B → A → ROOT

4. Left-child / right-siblingstruct { data, *firstChild, *nextSibling }

AfirstChild→BnextSibling→∅

BfirstChild→DnextSibling→C

CfirstChild→FnextSibling→∅

DfirstChild→∅nextSibling→E

EfirstChild→∅nextSibling→∅

FfirstChild→∅nextSibling→G

GfirstChild→∅nextSibling→∅

Same tree, four physical layouts. Notice how the array view costs zero pointers, the linked view spends two pointers per node, and the LCRS view spends two pointers regardless of branching factor — that's the trick that lets it represent any n-ary tree with the same per-node cost as a binary tree.

Pause on this picture. The same tree, the same operations, four wildly different physical encodings. The right answer to "which one should I use?" is always the same: the one whose dominant operation is cheapest in your workload. Sequential BFS on a complete tree? Array. Insert / delete anywhere, any shape? Linked. Union-find? Parent pointer. Arbitrary branching factor? LCRS. Coming from a graph context? Adjacency list.

C: Array-Based Binary Tree

Let's make the array representation concrete. The implementation below stores any binary tree of bounded height in a fixed-capacity flat buffer using only the heap-math relations.

Array-backed binary tree

📄c

Explanation(20)

Code(54)

1Standard headers

stdio.h gives us printf for the demo at the bottom. stdlib.h gives us malloc / calloc / free — every dynamic array in C goes through these.

4Sentinel for an empty slot

We pick the NUL byte as our sentinel value meaning 'no node here'. The implicit-array layout reserves a slot for every position 0..capacity-1, but a real tree may not be complete — slots that no node occupies must be distinguishable from real data. Using a sentinel keeps the representation pointer-free.

EXAMPLE

#define EMPTY '\0'   // any byte that cannot occur as real data works

6The struct: just three fields

An ArrayTree is essentially a fixed-capacity char buffer with a logical size. There is NO pointer-per-node bookkeeping — every relationship is computed by index arithmetic. That is the entire selling point of this layout.

7data: the backing buffer

A flat char array of length 'capacity'. Index i in this array represents node i in the tree's heap-order numbering. Reading data[3] reads node 3.

8capacity: the maximum nodes we can store

For a binary tree of height h, the maximum number of nodes is 2^(h+1) − 1. To support height 3 we need capacity 15. The array layout is great when this bound is tight (heaps, segment trees) and wasteful when the tree is skinny.

9size: how many nodes are actually present

We store the highest occupied index + 1. Walks like at_print stop here so we don't print empty trailing slots. size grows as we insert; it does NOT shrink on deletion in this minimal implementation.

12at_create — constructor

Allocates the wrapper struct + a zeroed buffer. Returns a fresh tree with size = 0. The convention 'caller frees' is standard C — we'll free both data and t in main.

14calloc zeros the buffer

Unlike malloc, calloc(n, sz) zero-initializes memory. Since our EMPTY sentinel IS the zero byte, every slot starts as 'unoccupied'. If we used a non-zero sentinel we'd need an explicit fill loop.

EXAMPLE

calloc(15, 1) gives us 15 zero bytes — all slots start EMPTY.

20parent_of: the famous (i-1)/2

Heap math: integer division rounds toward zero, so children at indices 2i+1 and 2i+2 both map back to i. This is the only piece of arithmetic you need to memorize for array-based trees.

EXAMPLE

parent_of(3) = (3-1)/2 = 1   parent_of(4) = (4-1)/2 = 1   ✓ (B has children D and E)

21left_of: 2i+1

Why 2i+1 and not 2i? Because we are 0-indexed. With 1-indexing the formula is 2i, but 0-indexing makes the C code simpler since arrays start at 0 already.

EXAMPLE

left_of(0) = 1   left_of(1) = 3   left_of(2) = 5

22right_of: 2i+2

Right child is the slot immediately after the left child. left_of(i) and right_of(i) differ by exactly 1 — that pair is contiguous in memory, which is good for cache lines when you stream both children together.

25at_set_root

Trivial helper. Index 0 is always the root by convention. We bump size to 1 if the tree was previously empty.

30at_set_left — the only insertion subtlety

We compute li = left_of(i). Two failure modes are checked: (a) li >= capacity means the tree would grow past the buffer; (b) the parent slot is EMPTY, meaning we'd be attaching a child to a non-existent node. Both return error codes; the caller decides how to react.

LOOP TRACE · 3 iterations

before at_set_left(t,0,'B')

data = ['A',0,0,0,...]

i = 0

li = 1

after at_set_left(t,0,'B')

data = ['A','B',0,0,...]

size = 2

after at_set_left(t,1,'D')

data = ['A','B',0,'D',0,0,...]

size = 4

32Capacity overflow check

Without this guard, a write to data[li] with li >= capacity is undefined behavior — typically heap corruption that crashes far away from the actual bug. Always bound-check before raw pointer writes.

33Hole check: cannot attach below an empty parent

If data[i] is EMPTY then index i has no node, and giving it a child would create a 'floating' subtree. We refuse. This invariant — children only exist below real nodes — is what makes the size accounting work.

EXAMPLE

Trying at_set_left(t, 5, 'X') when data[5]==EMPTY returns -2.

36Update size to highest live index + 1

li is now occupied. If li+1 exceeds the previous size, the tree just grew. Note we do NOT decrement size when nodes get removed — keeping size as a high-water-mark simplifies traversal at the cost of some empty slots inside.

41at_print walks 0..size-1 in array order

This is also a level-order (BFS) traversal for free — index order in a heap layout IS level order. That dual-meaning is the layout's hidden gift: BFS becomes a tight for-loop with no queue.

LOOP TRACE · 4 iterations

i=0

c = 'A'

stdout = [0]=A

i=1

c = 'B'

stdout = [0]=A [1]=B

i=2

c = EMPTY

stdout = [0]=A [1]=B [2]=.

i=3

c = 'D'

stdout = [0]=A [1]=B [2]=. [3]=D

49main — wire up the example

Capacity 15 supports a complete tree of height 3. We insert root A, left child B under A, then left child D under B. The print at the end shows all four occupied positions plus the one empty hole at index 2 (where C would go if we had inserted a right child under A).

53Print after three inserts

Output is exactly: [0]=A [1]=B [2]=. [3]=D — proving the layout: A occupies the root, B occupies the left-child-of-root slot, D occupies the left-grandchild slot, and the right-child-of-root slot at index 2 is empty.

54Free the backing buffer first, then the wrapper

Order matters: t->data was allocated separately from t. If we freed t first, t->data would be a dangling pointer. This is the standard 'destroy in reverse construction order' rule for C.

34 lines without explanation

1#include <stdio.h>
2#include <stdlib.h>
3
4#define EMPTY '\0'
5
6typedef struct {
7    char *data;     // backing buffer
8    int   capacity; // max nodes (2^h - 1 for height h)
9    int   size;     // logical node count
10} ArrayTree;
11
12ArrayTree *at_create(int capacity) {
13    ArrayTree *t = malloc(sizeof(ArrayTree));
14    t->data     = calloc(capacity, sizeof(char));   // EMPTY everywhere
15    t->capacity = capacity;
16    t->size     = 0;
17    return t;
18}
19
20static int parent_of(int i)      { return (i - 1) / 2; }
21static int left_of(int i)        { return 2 * i + 1;   }
22static int right_of(int i)       { return 2 * i + 2;   }
23
24void at_set_root(ArrayTree *t, char x) {
25    t->data[0] = x;
26    if (t->size == 0) t->size = 1;
27}
28
29int at_set_left(ArrayTree *t, int i, char x) {
30    int li = left_of(i);
31    if (li >= t->capacity) return -1;       // would overflow
32    if (t->data[i] == EMPTY) return -2;     // cannot attach to a hole
33    t->data[li] = x;
34    if (li + 1 > t->size) t->size = li + 1;
35    return li;
36}
37
38void at_print(const ArrayTree *t) {
39    for (int i = 0; i < t->size; i++) {
40        char c = t->data[i];
41        printf("[%d]=%c  ", i, c == EMPTY ? '.' : c);
42    }
43    printf("\n");
44}
45
46int main(void) {
47    ArrayTree *t = at_create(15);            // height up to 4
48    at_set_root(t, 'A');
49    at_set_left(t, 0, 'B');                  // -> [1]
50    at_set_left(t, 1, 'D');                  // -> [3]
51    at_print(t);                             // [0]=A [1]=B [2]=. [3]=D
52    free(t->data); free(t);
53    return 0;
54}

C: Linked Binary Tree

Now the pointer-based version. Notice how much more code there is for memory management — allocation, recursive freeing, NULL-checking — compared to the array version. Pointers buy flexibility but charge for it in book-keeping.

Linked binary tree with preorder traversal

📄c

Explanation(14)

Code(45)

4The recursive struct definition

In C a self-referential struct must use the tag form — 'struct Node *left' not 'Node *left' — because the typedef name 'Node' is not yet visible inside the struct body. The typedef on line 8 then introduces 'Node' as a shorthand for outside use.

5data field — the payload

We use char for simplicity. In real code this becomes whatever your tree carries: an int key, a struct of key+value, a pointer to an arbitrary record. The structure of the tree is independent of the payload type.

6left pointer

A pointer (8 bytes on 64-bit systems) to the left child Node, or NULL if there is none. NULL is the explicit signal for 'no child' — the linked layout uses it instead of a sentinel value in a flat buffer.

7right pointer

Symmetric to left. Together left and right take 16 bytes per node — that pointer overhead is the price you pay for a tree that can be any shape (skinny, balanced, spiky) without wasted slots.

11node_new — heap-allocate one node

Returns a pointer to a fresh node with the given data and both children set to NULL. Always initialize pointer fields explicitly — uninitialized pointers in C are not NULL by default; they are garbage, and dereferencing them is undefined behavior.

EXAMPLE

Node *n = node_new('A');   // n->data='A', n->left=NULL, n->right=NULL

13malloc the exact struct size

sizeof(Node) is computed at compile time and gives the right number of bytes regardless of platform alignment. Never hard-code struct sizes — adding a field would silently break the allocation.

19tree_free — recursive destructor

We free post-order: children before parent. If we freed the parent first we would lose the pointers to the children and leak them. The base case (NULL) terminates the recursion at the leaves' empty children.

20Base case: NULL pointer

The first thing every recursive tree function does is check for NULL. This handles two cases at once: leaves (whose children are NULL) and an empty tree. Forgetting this check is the single most common cause of segfaults in tree code.

21Recurse left, then right, then free self

Order matters for correctness, not for performance. As long as we free both children before freeing self, the order between left and right is interchangeable.

LOOP TRACE · 8 iterations

tree_free(A)

stack = [A]

tree_free(B)

stack = [A, B]

tree_free(D)

stack = [A, B, D]

free(D)

stack = [A, B]

freed = {D}

free(B)

stack = [A]

freed = {D, B}

tree_free(C)

stack = [A, C]

free(C)

stack = [A]

freed = {D, B, C}

free(A)

stack = []

freed = {D, B, C, A}

26preorder — root, left, right

Visits self FIRST, then recurses into children. This is the simplest traversal — its order corresponds to a top-down read of the tree. We'll cover traversals fully in section 3, but they're worth seeing once here to make the linked layout feel concrete.

27Print self before recursing

Swap this with the two recursive calls and you get postorder. Put it BETWEEN them and you get inorder. The position of the visit relative to the recursion is the entire definition of which traversal you're computing.

33Build the tree manually

We allocate four nodes, then wire them up with explicit pointer assignments. In production code you'd usually have a build_from_array helper — but doing it by hand once shows that nothing is hidden: the tree's shape is purely the pattern of pointers you set.

LOOP TRACE · 5 iterations

after A=node_new('A')

A = {data='A', left=NULL, right=NULL}

after B,C,D allocated

B = {'B', NULL, NULL}

C = {'C', NULL, NULL}

D = {'D', NULL, NULL}

after A->left=B

A = {'A', →B, NULL}

after A->right=C

A = {'A', →B, →C}

after B->left=D

B = {'B', →D, NULL}

41preorder(A) prints 'A B D C'

Visit A, recurse left into B, visit B, recurse left into D, visit D, D has no children so we return; back in B we recurse right (NULL) and return; back in A we recurse right into C, visit C. Final output: A B D C — exactly preorder.

43Free the entire tree before exit

main returning to the OS will reclaim the memory anyway, but in any non-trivial program we must free explicitly. Memory that 'leaks' inside a long-running process accumulates forever; that's why tree_free is part of the API.

31 lines without explanation

1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct Node {
5    char         data;
6    struct Node *left;
7    struct Node *right;
8} Node;
9
10Node *node_new(char x) {
11    Node *n = malloc(sizeof(Node));
12    n->data  = x;
13    n->left  = NULL;
14    n->right = NULL;
15    return n;
16}
17
18void tree_free(Node *root) {
19    if (root == NULL) return;
20    tree_free(root->left);
21    tree_free(root->right);
22    free(root);
23}
24
25void preorder(const Node *n) {
26    if (n == NULL) return;
27    printf("%c ", n->data);
28    preorder(n->left);
29    preorder(n->right);
30}
31
32int main(void) {
33    Node *A = node_new('A');
34    Node *B = node_new('B');
35    Node *C = node_new('C');
36    Node *D = node_new('D');
37    A->left  = B;
38    A->right = C;
39    B->left  = D;
40
41    preorder(A);                 // A B D C
42    printf("\n");
43    tree_free(A);
44    return 0;
45}

Python: Linked Binary Tree (From Scratch)

The Python version reads almost like pseudocode, but every operation has the same algorithmic content as its C counterpart. The differences are bookkeeping: Python garbage-collects so we don't write tree_free; $\text{None}$ replaces $\text{NULL}$ ; $\text{\_\_slots\_\_}$ gives us the memory profile of a struct.

Python TreeNode and recursive height

🐍python

Explanation(15)

Code(36)

1TreeNode class declaration

We model a binary tree node as a small class. Python doesn't need an explicit 'struct' — the class plays that role. Each instance owns three attributes: data, left, right.

3__slots__ — a memory optimization

Without __slots__, every Python object carries a per-instance __dict__ (typically 100+ bytes). Trees can have millions of nodes, so this matters. Declaring __slots__ tells Python: 'these are the only attributes; allocate them as fixed slots, no dict.' Saves ~50% memory per node on CPython.

EXAMPLE

Without __slots__: ~104 bytes/node
With    __slots__:  ~56 bytes/node

5__init__ takes only the data

A fresh node starts isolated — no children. The caller wires up the structure afterward by setting left and right. This matches the C pattern: node_new in C and TreeNode(...) in Python both produce a leaf you then connect.

6data field, type-annotated as object

Python is dynamically typed, but PEP 484 annotations document intent. 'object' here means 'anything' — int, str, custom class. If your tree only holds ints you'd narrow this to int and let mypy catch mistakes.

7left: typed as TreeNode | None

The forward reference 'TreeNode | None' (in quotes because TreeNode is not yet fully defined when the annotation is evaluated) tells type checkers a left child is either another TreeNode or None. This is the Python equivalent of C's NULL terminator.

10__repr__ for debug-friendly printing

Defining __repr__ makes print(node) and the REPL show TreeNode('A') instead of <TreeNode object at 0x...>. data!r calls repr on the data field, so strings get quoted properly. Tiny but invaluable when debugging tree structure.

EXAMPLE

print(TreeNode('A')) -> TreeNode('A')
print(TreeNode(42))  -> TreeNode(42)

14insert_left helper

Adding a left child is a one-liner, but wrapping it in a function gives us a place to enforce invariants. Here we refuse to overwrite an existing left child — that would silently leak the previous subtree. Returning the new node lets the caller chain operations.

16Reject overwriting an existing child

If parent.left already references a subtree and we just reassigned parent.left = TreeNode(data), Python's garbage collector would eventually free the old subtree — but if anything else references those nodes, we'd have inconsistent state. Raising is the safe default.

18Return the new node

This makes the API composable: parent.left = insert_left(parent, 'B') reads cleanly, and chains work — insert_left(insert_left(root, 'B'), 'D') builds a left spine.

22height — recursive depth computation

Definition: height of empty tree is −1, height of a leaf is 0, height of an internal node is 1 + max(height of children). The −1 base case makes the leaf case fall out of the recurrence cleanly: 1 + max(−1, −1) = 0.

23Base case: empty tree -> −1

Choosing −1 (not 0) as the empty-tree height is a convention with mathematical payoff: the formula height(n) = 1 + max(height(n.left), height(n.right)) then works uniformly for leaves, internal nodes, and all of their children.

EXAMPLE

height of leaf D = 1 + max(height(None), height(None)) = 1 + max(-1,-1) = 0

25Recurrence: 1 + max(left, right)

Adds 1 for the current node and takes the deeper of the two child subtrees. This is the definition of height, transcribed into Python with no creative additions.

LOOP TRACE · 4 iterations

height(D)

left = -1

right = -1

ret = 0

height(B)

left = height(D) = 0

right = height(None) = -1

ret = 1 + max(0,-1) = 1

height(C)

left = -1

right = -1

ret = 0

height(A)

left = height(B) = 1

right = height(C) = 0

ret = 1 + max(1,0) = 2

29Build the tree by direct attribute assignment

We could use insert_left, but for a fixed shape this is clearer. Note the structure mirrors the C version exactly: same four nodes, same parent/child relationships.

33print(A) -> TreeNode('A')

Calls __repr__. We don't see B, C, D here — only the root's data — because __repr__ is shallow on purpose. Printing the whole tree would obscure the focal node; for full-tree dumps you'd write a separate pretty-printer.

34height(A) -> 2

Trace: height(A) = 1 + max(height(B), height(C)). height(B) = 1 + max(height(D), -1) = 1. height(C) = 0. height(A) = 1 + max(1, 0) = 2. Matches the visual tree: A→B→D is the longest root-to-leaf path with 2 edges.

21 lines without explanation

1class TreeNode:
2    """A binary tree node with left and right child references."""
3    __slots__ = ("data", "left", "right")
4
5    def __init__(self, data):
6        self.data: object = data
7        self.left:  "TreeNode | None" = None
8        self.right: "TreeNode | None" = None
9
10    def __repr__(self) -> str:
11        return f"TreeNode({self.data!r})"
12
13
14def insert_left(parent: TreeNode, data) -> TreeNode:
15    """Attach a new node as the left child. Returns the new node."""
16    if parent.left is not None:
17        raise ValueError("left child already exists")
18    parent.left = TreeNode(data)
19    return parent.left
20
21
22def height(node: "TreeNode | None") -> int:
23    """Return the longest root-to-leaf path length. Empty tree -> -1."""
24    if node is None:
25        return -1
26    return 1 + max(height(node.left), height(node.right))
27
28
29# Build the same tree as the C example: A -> B (left D), C
30A = TreeNode("A")
31A.left  = TreeNode("B")
32A.right = TreeNode("C")
33A.left.left = TreeNode("D")
34
35print(A)                # TreeNode('A')
36print(height(A))        # 2

Python: Converting Between Representations

Real systems often need to switch between layouts. You might receive a tree as a flat JSON list (heap-order array), build a linked structure to operate on it, then re-flatten for transmission. The two conversion routines below let you round-trip:

linked_to_array and array_to_linked

🐍python

Explanation(18)

Code(42)

1linked_to_array — write a tree into heap layout

Takes a TreeNode root and produces a list whose indices follow heap-order numbering. This conversion is essential whenever you need to serialize a tree for storage, network transmission, or interop with array-based APIs (priority queues, segment trees).

2Default capacity 63 = 2^6 − 1

Chosen to support trees of height up to 5. Caller can override. We need an explicit ceiling because the array layout cannot grow lazily — every reachable index up to 2^(h+1)−1 must be addressable.

8Initialize with None placeholders

Slots that no node occupies stay None. None is Python's natural sentinel for 'absent'. Compare to C, where we used '\0' — Python doesn't need a special byte because list elements can hold any reference, and None compares unambiguously.

9Empty-tree shortcut

If the root is None we return [None, None, ..., None]. Some serializers prefer an empty list — both conventions work; pick one and document it.

13BFS with (node, index) pairs

Plain BFS would visit nodes in level order but lose the heap-index. Storing index alongside node propagates the heap math: a node at index i pushes children at 2i+1 and 2i+2.

EXAMPLE

Initial queue: [(A, 0)]
After visiting A: [(B,1), (C,2)]
After B: [(C,2), (D,3)]

14queue.pop(0) — FIFO from the front

list.pop(0) is O(n) because Python lists are array-backed. For correctness it's fine; for performance a deque would be O(1). We keep list for readability — production code should use collections.deque.

15Capacity check

If a node's heap index exceeds capacity, the tree is too tall for the buffer. We raise rather than silently truncating. This is the array layout's fundamental limitation surfacing as an explicit error.

EXAMPLE

A 100-node skinny tree (each node has one child) needs capacity 2^99 — completely impractical.

17Write the data, not the node

We store node.data, not the node itself, because the array is meant to be a self-contained snapshot. Writing the node would create cyclic references (the array references nodes which reference each other) — bad for serialization.

18Push left child with index 2i+1

If the current node has a left child, that child belongs at heap index 2i+1. We append (child, child_index) to the queue. The 'if not None' guard prevents pushing absent children.

19Push right child with index 2i+2

Symmetric to left. Together these two lines are the only place the heap formula appears in the BFS loop — that single pair of expressions is what propagates the heap layout.

LOOP TRACE · 4 iterations

pop (A,0); arr[0]='A'; push (B,1),(C,2)

arr[0..6] = ['A',N,N,N,N,N,N]

pop (B,1); arr[1]='B'; push (D,3)

arr[0..6] = ['A','B',N,N,N,N,N]

pop (C,2); arr[2]='C'; (no children)

arr[0..6] = ['A','B','C',N,N,N,N]

pop (D,3); arr[3]='D'; (no children)

arr[0..6] = ['A','B','C','D',N,N,N]

23array_to_linked — reverse direction

Materializes a linked tree from a heap-order array. The two-pass strategy (build all nodes, then wire them) avoids ordering issues that would crop up if we tried to do both at once.

24Empty input check

If the array is empty or its first slot is None, the represented tree is empty — we return None. This matches linked_to_array's empty-tree case so that round-tripping an empty tree gives None.

26Pass 1: allocate every non-None slot

List comprehension creates len(arr) nodes (or None for empty slots). After this pass nodes[i] is the freshly-allocated TreeNode for arr[i], or None. No pointers wired yet.

EXAMPLE

arr = ['A','B','C','D',None,None,None]
nodes = [Node('A'), Node('B'), Node('C'), Node('D'), None, None, None]

28Pass 2: wire children using heap math

For each occupied slot i, look at indices 2i+1 and 2i+2. If those positions exist AND hold a node, set nodes[i].left and nodes[i].right accordingly. The bound check 'l < n' prevents indexing past the array.

32Return root = nodes[0]

Heap convention: index 0 is the root. We don't return the entire nodes list because callers expect a tree (a single root reference) — they can walk from there to reach any other node.

36Round-trip test: linked → array → linked

Build the array, then rebuild a fresh linked tree from it. The new tree should be structurally identical to the original. We verify by reaching B_again.left.left.data and checking it's 'D' — meaning the heap math placed D back at index 3 and the wiring restored the A→B→D path.

37flat[:7] -> ['A','B','C','D',None,None,None]

First seven slots show the level-order encoding of our tree. Slots 4–6 are None because B's right child and both of C's children are absent. This view makes the heap layout's wastefulness visible: a small unbalanced tree leaves holes.

39B_again.left.left.data -> 'D'

Two pointer hops from the new root reach the rebuilt D node. Round-trip succeeded — the array form preserves the structure exactly, modulo the limitation that we cannot distinguish 'no node here' from 'a node holding the value None'.

24 lines without explanation

1def linked_to_array(root, capacity=63):
2    """Serialize a binary tree into heap-order array layout.
3
4    Slot i holds the node whose path from the root is encoded by i's
5    binary digits (skipping the leading 1): 0=L, 1=R. Empty positions
6    hold None.
7    """
8    arr = [None] * capacity
9    if root is None:
10        return arr
11
12    # BFS, tracking each node's heap-order index.
13    queue: list = [(root, 0)]
14    while queue:
15        node, i = queue.pop(0)
16        if i >= capacity:
17            raise IndexError(f"capacity {capacity} too small")
18        arr[i] = node.data
19        if node.left  is not None: queue.append((node.left,  2*i + 1))
20        if node.right is not None: queue.append((node.right, 2*i + 2))
21    return arr
22
23
24def array_to_linked(arr):
25    """Rehydrate a heap-order array into a linked tree."""
26    if not arr or arr[0] is None:
27        return None
28    nodes = [TreeNode(v) if v is not None else None for v in arr]
29    n = len(arr)
30    for i in range(n):
31        if nodes[i] is None: continue
32        l, r = 2*i + 1, 2*i + 2
33        if l < n: nodes[i].left  = nodes[l]
34        if r < n: nodes[i].right = nodes[r]
35    return nodes[0]
36
37
38# Round-trip test
39flat = linked_to_array(A, capacity=15)
40print(flat[:7])             # ['A', 'B', 'C', 'D', None, None, None]
41B_again = array_to_linked(flat)
42print(B_again.left.left.data)   # 'D'

Cost of Every Representation

With $n$ nodes and tree height $h$ , the operations break down as follows. Cells marked — mean the operation is not directly supported and would require building an auxiliary data structure first.

Operation	Array	Linked	Parent-ptr	LCRS	Adj. list
access root	O(1)	O(1)	O(1)	O(1)	O(1)
go to left/right child	O(1)	O(1)	—	O(1) / O(deg)	O(1)
go to parent	O(1)	O(h) without ptr / O(1) with	O(1)	O(h)	—
enumerate all children	O(1) per slot	O(1) per child	O(n)	O(deg)	O(deg)
insert at known position	O(1) if slot free	O(1)	O(1)	O(1)	O(1) amort.
delete a leaf	O(1)	O(1) with parent ref	O(1)	O(deg) to unlink	O(deg)
BFS / level order	O(n)	O(n) with queue	O(n)	O(n)	O(n)
DFS	O(n)	O(n) with stack/recursion	O(n)	O(n)	O(n)
bytes per node (64-bit, char data)	1	16-24	5	16	16-24
wastes slots on unbalanced trees?	yes (exponentially)	no	no	no	no

Read the bottom row carefully. The array layout's memory consumption is worst case $O(2^h)$ , while every other representation uses $O(n)$ . For a balanced tree of $n$ nodes, $h \approx \log_2 n$ so $2^h \approx n$ and the array is fine. For a skinny tree (worst-case BST insertion order), $h = n - 1$ and the array layout is catastrophically wasteful.

Memory Model: Cache, Pointers, and Locality

Big-O hides constants. On real hardware, two operations both labeled $O(1)$ can differ by an order of magnitude depending on cache behavior. Tree representations differ wildly here.

The array layout is a streaming workload

When you traverse an array-based heap in level order, you read consecutive memory addresses. CPUs prefetch the next cache line before you ask for it; the inner loop runs at L1 speed. A modern CPU L1 cache hit costs about $4$ cycles, an L2 hit about $12$ , an L3 hit about $40$ , a DRAM access about $200$ . Sequential reads over a 40 MB array stay in L2/L3 most of the time.

The linked layout is a pointer-chase

Each node is independently malloc'd, so neighboring nodes in the tree are not neighboring in memory. Following $\text{node->left}$ is a load of an address you cannot predict, then a load of memory at that address. The prefetcher cannot help; every dereference is a potential L3 miss. For a tree that doesn't fit in cache, the constant factor on every "go to child" can be $50\times$ the array equivalent.

This is why high-performance libraries like B-trees, LSM-trees, and database indexes use wide, shallow, array-packed nodes — they're trying to recover the array layout's cache friendliness while keeping the linked layout's flexibility.

Where Each Representation Lives in Real Systems

Array layout in the wild

Binary heap — the priority queue inside every operating-system scheduler, every Dijkstra implementation, every event-driven simulator. Insert and extract-min run in $O(\log n)$ with no pointers and great cache behavior.
Segment tree / Fenwick tree — competitive programming's favorite range-query structure, always built on a flat array of size $4n$ or $2n$ .
NumPy/PyTorch internal storage of complete trees — reduction kernels on GPUs treat thread blocks as a balanced binary tree implicitly indexed by thread ID.

Linked layout in the wild

Browser DOM — every $\langle \text{div} \rangle$ is a heap-allocated object with parent and children references. The shape changes every frame, so flexibility wins over memory.
std::map and std::set — libc++ and libstdc++ implement these as red-black trees with linked nodes (each node carries 3 pointers + color bit + payload).
Compiler ASTs — clang, GCC, V8, the Rust compiler all build linked tree-of-nodes structures because syntax trees have wildly variable shape.

Parent-pointer layout in the wild

Union-find / disjoint-set in Kruskal's MST, image-segmentation watersheds, and incremental connectivity. Path compression mutates the parent array itself.
Process tree in the kernel — $\text{task\_struct.real\_parent}$ is a single pointer per process; children are a separate intrusive list, but the parent direction is what matters for signal delivery.
Git's commit graph — each commit stores its parent commit hash(es), no list of children. Walking history goes backward only, exactly as expected.

LCRS in the wild

Classic Unix directory entries — older filesystems chain children of a directory through linked sibling pointers.
XML / SGML / HTML parsers emitting events without pre-allocating arrays.
Compiler IR for languages with unbounded children per AST node (e.g. $\text{Lisp s-expressions}$ ) where $(\text{first}, \text{rest})$ IS the LCRS encoding.

Adjacency list in the wild

Spanning trees from BFS / DFS — you already had the graph in adjacency-list form, so the spanning tree comes out the same way.
Phylogenetic trees in bioinformatics — the Newick format and most analysis pipelines pass trees as labeled edge lists.
Social-network friend hierarchies — reporting trees, recommendation subtrees, anything coming out of a graph database.

Pitfalls and Edge Cases

Heap-array overflow on skinny trees. The array layout sizes by

2^{h+1} - 1

, not by

n

. Inserting

n = 30

nodes into a worst-case skewed tree requires a buffer of

2^{30} \approx 10^9

slots. Never use the array layout unless you can prove the tree stays close to balanced.

Forgetting to free children before parents. In C, freeing a parent then recursing into its (now-dangling)

\text{left}

pointer is undefined behavior. Always recurse first, free last. The same logic applies to reference-counted languages (Rust's

\text{Rc}

) when you manually break cycles.

Confusing "empty slot" with "node holding zero/None" in the array layout. If your payload type can legitimately be zero or None, using the zero/None value as the empty-slot sentinel collides with real data. Either reserve a special bit, use a parallel boolean array, or use Optional<T> explicitly.

Iterating children in LCRS or adjacency list reverses cheaply but random-accesses expensively. Asking "the 5th child of this node" costs

O(5)

in LCRS (walk five sibling pointers), versus

O(1)

in an adjacency list backed by a vector. If you do random child indexing, prefer the vector.

Parent-pointer arrays cannot answer "list children" cheaply. Don't pick this layout if your dominant query is downward enumeration. If you need both directions, store both arrays —

\text{parent}[]

and a list of

\text{children}[]

— even though it doubles the structural memory.

Quick Checks

Quick Check

A complete binary tree has 31 nodes (heights 0..4 all full). In the heap-array layout, what is the index of the parent of node 25?

Quick Check

You are implementing union-find on 10 million elements. Which representation should you pick?

Quick Check

What is the per-node memory overhead (in bytes, on a 64-bit machine) of an LCRS encoding versus a 5-ary tree that stores its children in a fixed-size array?

Quick Check

A tree has 8 nodes and is laid out as a heap-order array. Slot 7 contains 'X'. Where is X's parent in the array?

Quick Check

You are profiling a tree traversal and find that 80% of the time is spent on cache misses during pointer dereferences. The tree shape is roughly balanced and rarely changes. What is the best mitigation?