Representation

A tree is a set of nodes plus one relation: who is whose child. Every representation you will ever meet is a different answer to one question - where do you keep that relation? There are only three places to keep it, so there are only three families, and the first thing you do with a tree depends entirely on which family you were handed.

Tree Anatomy is about what a tree is; this page is about where it is stored.

1. Where the links can live

One tree, three families. The nodes and the shape are identical in all three; only the location of the parent-child relation changes.

Family	Where the links live	Max degree	Direction it walks	Cost
In the node	Fields on the node itself	Fixed by the class, or unbounded with a list	Down only	O(n)
In the index	Nowhere - the position implies it	Fixed by the arithmetic	Both, by arithmetic	O(2^h) with holes, O(n) without
As separate data	A list of pairs, outside the nodes	Unbounded	Neither, until you pick a root	O(n)

Representation decides direction, and direction decides the algorithm.

Node fields go down, parent arrays go up, edge lists go nowhere until you commit to a root, and index arithmetic goes anywhere but only for shapes dense enough to afford it. Before writing a line, ask which way this problem needs to move - most of the "how do I even start" feeling on tree problems is that question left unanswered.

2. Links in the node

Each node stores references to its own children. This is the family nearly every tree problem uses, and it comes in exactly two shapes, which differ only in whether the degree is baked into the type.

Fixed degree, the binary case:

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

Unbounded degree, the n-ary case:

class Node:

def __init__(self, val=0, children=None):

self.val = val

self.children = children or []

Three facts about both of them that decide how your code has to be written:

• There is no parent pointer. You cannot walk up. Anything that needs an ancestor either carries the path down with it or is solved bottom-up on the way back out of the recursion.
• There is no size, height or depth field. Any of those cost a traversal each time you want them, which is where accidental O(n^2) comes from.
• None is the empty tree, and it is a legal tree. Every function must answer for it. That is the base case.

A TreeNode reference is a tree, not a piece of one.

node.left is not "the left part of this tree" - it is a complete, smaller tree that your function already knows how to handle. Internalising this is what makes tree recursion stop feeling like a trick.

The only structural difference in the code is two named recursive calls versus one loop:

def size(node): # binary

if not node:

return 0

return 1 + size(node.left) + size(node.right)

 

def size(node): # n-ary

if not node:

return 0

return 1 + sum(size(c) for c in node.children)

⚠

left/right bakes the degree into the type

A class with left and right cannot hold a node with three children, and no amount of care at the call site changes that. This is why "convert an n-ary tree to a binary tree" (LeetCode 431) is a real problem rather than a cast: you have to re-encode, usually left-child/right-sibling, where left means "my first child" and right means "my next sibling". The children list has no such ceiling, which is why every general-tree algorithm is written against it.

3. Links in the index

Store nothing. Put node i at array position i and let arithmetic answer every structural question:

left(i) = 2i + 1

right(i) = 2i + 2

parent(i) = (i - 1) // 2

For a k-ary tree the same trick generalises to k*i + 1 ... k*i + k, which is the honest limit of this family: the arithmetic needs a fixed maximum degree decided in advance.

Because the position of every node is forced, an absent node still occupies its slot, and so do all the slots its descendants would have had. Those are the holes, and they are None:

A right-leaning chain with one added left child. The positional array must still reserve every slot the shape implies, so four nodes cost seven cells and three of them are holes.

The hole count is the whole story of this family. A tree of height h needs 2^(h+1) - 1 cells no matter how few nodes it actually has, so the cost runs from perfect to unusable depending only on shape:

Shape	Nodes	Cells needed	Holes
Complete	n	n	none
Typical / balanced	n	~2n	a constant fraction
One node per level (skewed)	n	2^n - 1	almost all of them

A 30-node right-leaning chain needs over a billion cells. That single line is why this representation is confined in practice to shapes that are guaranteed dense.

The heap array is not a fourth representation - it is this one, on a complete tree.

When the tree is complete, "reserve every slot the shape implies" and "pack the nodes contiguously" are the same instruction, so the holes vanish on their own and the array is exactly n cells. Nothing about the encoding changed; only the shape did. That is why heaps and segment trees maintain completeness as an invariant rather than as a nicety: completeness is what makes their storage O(n).

This family is also the only one that gives you a parent for free, without storing anything, which is what makes sift-up possible in a heap.

⚠

This is not the [1,null,2,3] from a problem statement

A positional array and the null-padded array a problem hands you are different encodings that look alike, and confusing them is the most common tree-input bug there is. Here, a null is a reserved slot and 2i+1 always holds. In the problem-statement form, a null is a terminator that consumes one entry and no more, and 2i+1 is meaningless. That form is a wire format, not a representation, and you decode it with a queue.

4. Links as separate data

Keep the nodes dumb and store the relation beside them, as its own array. This is the family that is natively general: nothing here has a fixed degree, and none of it assumes binary.

Edge list. n and a list of n - 1 undirected pairs. There is no root, no .left, and no direction: it is a free tree, and this is how graph-flavoured tree problems are posed.

The same five nodes, twice. The edge list has no top; rooting at 0 is a choice you make, and rooting at 3 would produce a different set of parents from the same input.

Rooting it is one BFS, and it hands you back the other two members of this family at once:

def root_tree(n, edges, root=0):

adj = [[] for _ in range(n)]

for u, v in edges:

adj[u].append(v)

adj[v].append(u) # undirected: BOTH directions

 

parent = [-1] * n

order = [] # nodes in BFS order, parents first

q = deque([root])

parent[root] = root # sentinel so the skip test is uniform

while q:

u = q.popleft()

order.append(u)

for v in adj[u]:

if v != parent[u]: # the one neighbour going back up

parent[v] = u

q.append(v)

parent[root] = -1

return parent, order

Mnemonic

order reversed is a postorder. A BFS from the root visits every parent before its children, so walking order backwards visits every child before its parent. That gives you bottom-up tree DP with no recursion and no stack depth limit, which is the standard way to do subtree sums on a 100000-node tree in Python.

Parent array. parent[i] is the index of i's parent, with -1 for the root. Compact, and the natural output of union-find. It walks up for free and down not at all: finding a node's children means scanning the whole array, unless you invert it first.

Children list. children[i] is a list of i's children - the same shape as the n-ary Node from section 2, with indices in place of references. Inverting a parent array into one is four lines:

children = [[] for _ in range(n)]

root = -1

for i, p in enumerate(parent):

if p == -1:

root = i

else:

children[p].append(i)

⚠

A parent array can encode something that is not a tree

parent is only a tree if it has exactly one -1 and no cycles. Two roots make it a forest; a cycle (parent[a] = b, parent[b] = a) makes it not a tree at all, and a naive "walk up to the root" loop will hang on it rather than crash. If the array is untrusted input - LeetCode 1666 and the "validate the tree" family - check both conditions before you walk it. For an edge list the matching check is cheaper: exactly n - 1 edges and connected.

⚠

The parent skip fails on a multigraph

if v != parent[u] skips the edge you came in on - and also skips a second, parallel edge to the same parent. On a genuine tree that is fine, because a tree has no parallel edges. On untrusted input it is not, and the fix is to skip by edge index rather than by node id. Real trees in problem statements are guaranteed simple, so the short form is correct; know why it is correct rather than assuming it always is.

5. Converting between the three

You are rarely stuck with the family you were handed. Whatever a problem gives you, converting into the family the next step wants is usually a single traversal, not a rewrite:

You have	You need	How
Index array (heap array)	Node links	Recurse (or loop) with left(i)=2i+1, right(i)=2i+2, building a real TreeNode at each index that is not a hole.
Node links	Separate data (edge list)	One DFS, appending [node.val, child.val] for every non-null child it visits.
Separate data (parent array)	Node links	Invert to a children list (section 4), then one BFS from the root building a TreeNode per index and wiring node.children.

The parent-array conversion is worth seeing in full, because it is the one interviews actually ask for - union-find and "build a hierarchy from a flat parent[i] column" both hand you exactly this input:

def build_tree(parent):

n = len(parent)

children = [[] for _ in range(n)]

root = -1

for i, p in enumerate(parent):

if p == -1:

root = i

else:

children[p].append(i)

 

nodes = [Node(i) for i in range(n)] # one pass: allocate every node

for i in range(n):

nodes[i].children = [nodes[c] for c in children[i]]

return nodes[root]

Allocate every node before you wire any of them together.

The single pass that builds nodes has to run to completion first - wiring nodes[i].children one node at a time, interleaved with allocation, means a child can be wired in before its own Node object exists whenever children[i] names an index you have not reached yet. Two passes, not one, is the fix for that entire class of bug.

6. Wire formats

A wire format is neither of the three families above - it is what a tree looks like flattened into text or a single array for transport, the way a problem statement or a network payload hands you one. You always decode it into node links (or an index array, if it is dense) before doing anything else with it; you never compute directly on the wire form.

The level-order array with null holes, [1,null,2,3] and its kin, is the one nearly every problem statement uses. It looks exactly like the index array from section 3, and that resemblance is the trap the gotcha there names: here, null is a terminator that consumes one array slot and stops, not a reserved position that index arithmetic can still find with 2i+1. Decoding it needs a queue, not arithmetic:

def deserialize(data): # data: [1, None, 2, None, 3]

if not data or data[0] is None:

return None

it = iter(data)

root = TreeNode(next(it))

queue = deque([root])

while queue:

node = queue.popleft()

left_val = next(it, None)

if left_val is not None:

node.left = TreeNode(left_val)

queue.append(node.left)

right_val = next(it, None)

if right_val is not None:

node.right = TreeNode(right_val)

queue.append(node.right)

return root

The preorder string with a sentinel, e.g. "1,2,#,#,3,4,#,#,5,#,#", is the other common wire format - the one LeetCode 297 (Serialize and Deserialize Binary Tree) asks you to design yourself. It trades the queue for recursion: a # (or any agreed sentinel) marks an absent child exactly where preorder would have visited it, so decoding is the mirror of encoding, one recursive call per token:

def serialize(root):

if not root:

return '#'

return f'{root.val},{serialize(root.left)},{serialize(root.right)}'

 

def deserialize(data):

values = iter(data.split(','))

def build():

val = next(values)

if val == '#':

return None

node = TreeNode(int(val))

node.left = build()

node.right = build()

return node

return build()

⚠

Trailing nulls are not guaranteed to be trimmed

A level-order array may or may not have its trailing nulls trimmed, depending on who produced it. [1,2,3,null,null,null,null] and [1,2,3] describe the same tree; the decode loop above handles both because next(it, None) treats "ran out of array" the same as "explicit null". Do not write a decoder that assumes the array's length matches 2^(h+1) - 1 exactly.

7. Which representation for which problem

The family you should be working in is usually named by the problem before you write a line - not by preference, by what the parameter list and the operations you need actually cost:

What you are given or need	Work in	Why
A TreeNode root parameter	Node links	The default entry point for almost every LeetCode tree problem; section 2.
n and edges = [[a,b], ...]	Separate data, then root it	No root is implied. One BFS (section 4) gets you a parent array and a node-links tree at once.
A parent[i] array, or union-find output	Separate data as-is, or invert to node links	Already rooted. Stay in it for O(1) ancestor lookups; invert only if you need to walk down.
Heap push/pop, or the problem says "complete tree"	Index array	Density is guaranteed, so the O(n)-cell bound from section 3 holds and arithmetic beats pointer-chasing.
[1,null,2,3] in the problem statement text	Decode the wire format first (section 6)	It is serialization, not a family you compute on directly.
Repeated "find the parent of" queries	Node links plus a precomputed parent array (or a .parent field)	Plain node links cannot walk up (section 2); build the missing direction once, rather than per query.

When in doubt, convert to node links and start there.

It is the family every traversal in the next page is written against, it is what recursion reads most naturally, and it is a one-pass conversion away from every other family (section 5). Stay in a different family only when the problem's cost profile specifically rewards it - a heap's O(1) parent, or union-find's O(1) leader lookups - not by default.

Where to go next

• Traversal and Recursion - now that you can get a tree, walk it: one depth-first route with three visit slots, plus level order, and the recursion shapes that go in those slots.
• Heaps - the index family with no holes, put to work.