Data structure 9 of 12

Trees and binary trees

A tree is a hierarchy: one node at the top, each node pointing down to its children. Every node with everything below it is a smaller tree, which is why tree code is almost always recursive.

A 3-minute conversation: Sam asks, Priya explains

0:00 / 2:33

Follow along on the page Pause on “your turn” questions

Sam Trees. Everyone says tree problems are all recursion.
Priya Because every node, together with everything below it, is a smaller tree. Solve the problem for the two smaller trees, combine with the root, and you're done.
Priya Think of the folders on your computer. One top folder, folders inside it, folders inside those, until you reach files. To count every file, count the files in each sub-folder the same way and add them up.
Sam The vocabulary?
Priya The root is the top node. Children are directly below a node, which is their parent. A leaf has no children. A subtree is a node with everything below it. And a binary tree gives each node at most two children, left and right.
Sam How is it stored?
Priya Each node is a small object with a value and references to its left and right children, None when missing. And LeetCode writes trees as a list, level by level, with null for a missing child.
Sam Costs?
Priya Visiting every node is linear. A plain binary tree has no order, so finding a value is linear too. And recursion uses one stack frame per level on the current path: about log n when balanced, up to n when the tree is a long chain.
Priya Your turn. Given the heights of the left and right subtrees, what's the height of the tree?
Priya One plus the larger of the two. Height follows the deepest single path.
Sam Any built-in tree?
Priya None for interviews. Problems give you a small TreeNode class.
Sam The players?
Priya Building a tree from LeetCode's list, handing out children in order with a queue. Counting the nodes: one for me, plus the left count, plus the right count. And height: one plus the max of the children.
Sam That's the same recipe twice.
Priya Exactly. Empty node: return the answer for an empty tree. Ask both children. Combine. Almost every tree problem fits it.
Sam Memory hook?
Priya Folders inside folders. Empty? Base case. Ask left, ask right, combine.
Sam Problems?
Priya Univalued binary tree, passing the root's value down and combining answers with "and". And sum of left leaves, where the parent tells each child which side it's on.
Sam Mistakes?
Priya No base case for an empty node. Mixing up height and depth. Recomputing the same subtree twice. Very deep, unbalanced trees. And reading LeetCode's list as heap positions.
Sam Next?
Priya Lesson ten, binary search trees: trees with an ordering rule.

1. What it is

The folders on your computer. One top folder; inside it, more folders; inside those, more again, until you reach files with nothing inside. To count every file, you count the files in each sub-folder the same way and add them up.

A tree is made of nodes joined by edges. The vocabulary you will see in every problem:

Root: the top node. Children: the nodes directly below a node; it is their parent.
Leaf: a node with no children. Subtree: a node together with everything below it.
Depth of a node: edges from the root down to it. Height of a tree: the most nodes on any root-to-leaf path (LeetCode's "maximum depth").
A binary tree gives each node at most two children, left and right. Most interview trees are binary.

2. How it sits in memory

Each node is a small object holding a value and references to its left and right children (None when missing). The whole tree is reached through one reference: the root.

LeetCode writes trees as a list read level by level, left to right, with null for a missing child: [3, 9, 20, null, null, 15, 7]. The page's first operation turns that list into real nodes.

3. Operations and what they cost

Task	Cost	Why
Visit every node	`O(n)`	Each node once.
Height, count, sum, find a value	`O(n)`	A plain binary tree has no order to exploit (a search tree does: structure 10).
Recursion depth	`O(h)` stack frames	h is the height: about log n when balanced, up to n when the tree is a long chain.
Reach a child	`O(1)`	Follow `left` or `right`.
Reach the parent	not possible directly	Nodes don't point up; carry the parent in your recursion if you need it.

The recursive recipe1. If the node is empty, return the answer for an empty tree. 2. Ask both children for their answers. 3. Combine them with this node's value. Almost every tree problem fits.

4. In Python, TypeScript and Java

No language has a built-in binary tree for interviews; problems give you a node class like this one.

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

    #      3
    #     / \
    #    9   20
    #       /  \
    #      15   7
    root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
    print(root.right.left.val)    # 15

class TreeNode {
      val: number; left: TreeNode | null; right: TreeNode | null;
      constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
      }
    }
    const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
    console.log(root.right!.left!.val);   // 15

class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    TreeNode root = new TreeNode(3);
    root.left = new TreeNode(9);
    root.right = new TreeNode(20);
    root.right.left = new TreeNode(15);
    root.right.right = new TreeNode(7);
    System.out.println(root.right.left.val);   // 15

5. Core operations, step by step

Build a tree from LeetCode's list, then the two shapes of recursion you'll write constantly: visiting every node, and combining answers from the children.

A · Build a tree from a level-order list

What it doesCreates the root, then hands out children to nodes in the order they were created, using a queue.

Picture itFilling seats row by row in a theatre: each person in the queue gets the next two seats behind them, or an empty seat where the list says null.

CostO(n).

The code. You rarely write this in an interview, but knowing it makes LeetCode's tree lists readable.

def build(vals):
    root = TreeNode(vals[0])
    q = deque([root])
    i = 1
    while i < len(vals):
        node = q.popleft()
        if vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

function build(vals: (number | null)[]): TreeNode {
  const root = new TreeNode(vals[0]!);
  const q: TreeNode[] = [root];
  let i = 1, head = 0;
  while (i < vals.length) {
    const node = q[head++];
    if (vals[i] !== null) {
      node.left = new TreeNode(vals[i]!);
      q.push(node.left);
    }
    i++;
    if (i < vals.length && vals[i] !== null) {
      node.right = new TreeNode(vals[i]!);
      q.push(node.right);
    }
    i++;
  }
  return root;
}

static TreeNode build(Integer... vals) {
    TreeNode root = new TreeNode(vals[0]);
    Deque<TreeNode> q = new ArrayDeque<>(List.of(root));
    int i = 1;
    while (i < vals.length) {
        TreeNode node = q.pollFirst();
        if (vals[i] != null) {
            node.left = new TreeNode(vals[i]);
            q.offerLast(node.left);
        }
        i++;
        if (i < vals.length && vals[i] != null) {
            node.right = new TreeNode(vals[i]);
            q.offerLast(node.right);
        }
        i++;
    }
    return root;
}

Line by line.

Line	What it does	Why
`node = q.popleft()`	The next node waiting for children.	Nodes receive children in the order they were created: level by level.
`if vals[i] is not None`	A real left child?	null means this node has no left child; nothing joins the queue.
`i += 1`	Move along the list after each child slot.	Both slots consume a list entry, even null ones.

Watch it run. [3, 9, 20, null, null, 15, 7].

Watch out for:

Treating the list as heap positions. LeetCode lists skip the children of missing nodes, so index 2i + 1 isn't always the left child.

B · Visit every node (count them)

What it doesCounts the node itself plus the counts of both subtrees.

Picture itCounting files: each folder reports 1 for itself plus whatever its sub-folders report.

CostO(n) time, O(h) stack.

The code. The recursive recipe in its smallest form.

def count(node):
    if node is None:
        return 0
    left = count(node.left)
    right = count(node.right)
    return 1 + left + right

function count(node: TreeNode | null): number {
  if (node === null) {
    return 0;
  }
  const left = count(node.left);
  const right = count(node.right);
  return 1 + left + right;
}

static int count(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = count(node.left);
    int right = count(node.right);
    return 1 + left + right;
}

Line by line.

Line	What it does	Why
`if node is None: return 0`	An empty tree has no nodes.	This base case is where every path of recursion stops.
`left = count(node.left)`	Ask the left subtree.	Trust the recursion: it returns the right answer for the smaller tree.
`return 1 + left + right`	Me plus both subtrees.

Watch it run. Count the nodes of [3, 9, 20, null, null, 15, 7].

Watch out for:

Forgetting the None case. node.left on None crashes. Check for an empty node first.

C · Combine answers from the children (height)

What it doesHeight = 1 + the taller of the two subtrees' heights.

Picture itHow deep is the folder tree? One for this folder, plus the deepest sub-folder chain.

CostO(n) time, O(h) stack.

The code. Same recipe; only the combining line changes.

def height(node):
    if node is None:
        return 0
    left = height(node.left)
    right = height(node.right)
    return 1 + max(left, right)

function height(node: TreeNode | null): number {
  if (node === null) {
    return 0;
  }
  const left = height(node.left);
  const right = height(node.right);
  return 1 + Math.max(left, right);
}

static int height(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = height(node.left);
    int right = height(node.right);
    return 1 + Math.max(left, right);
}

Line by line.

Line	What it does	Why
`return 1 + max(left, right)`	One for me, plus the deeper side.	Use max, not +: height follows one path, not both.

Watch it run. The height of [3, 9, 20, null, null, 15, 7].

Watch out for:

Adding left and right. That counts nodes on both sides, not the longest path.
Returning −1 or 0 for a leaf by mistake. Decide what an empty tree returns (0 here), and a leaf follows: 1 + max(0, 0) = 1.

6. How to remember it

Memory hook: "Folders inside folders"Every folder is a smaller copy of the whole. Ask each sub-folder for its answer, combine with your own, and the empty folder is where you stop.

Picture

A file explorer with folders expanded, each folder reporting a number up to its parent.

Chant

"Empty? Base case. Ask left, ask right, combine."

Key rule

Height takes the max of the children; counts and sums add them.

7. Problems solved with it

Two easy problems: one asks the children a yes/no question, the other passes information down.

LC 965 · Univalued Binary Tree

The problemReturn true if every node in the tree has the same value.

What it doesEach subtree must be univalued with the root's value.

CostO(n).

The code. Pass the value to match down; combine the children's answers with and.

def is_unival(node, value):
    if node is None:
        return True
    if node.val != value:
        return False
    return is_unival(node.left, value) and is_unival(node.right, value)

function isUnival(node: TreeNode | null, value: number): boolean {
  if (node === null) {
    return true;
  }
  if (node.val !== value) {
    return false;
  }
  return isUnival(node.left, value) && isUnival(node.right, value);
}

static boolean isUnival(TreeNode node, int value) {
    if (node == null) {
        return true;
    }
    if (node.val != value) {
        return false;
    }
    return isUnival(node.left, value) && isUnival(node.right, value);
}

Line by line.

Line	What it does	Why
`if node is None: return True`	An empty subtree breaks nothing.
`if node.val != value: return False`	A different value: the answer is no.	Stop early; no need to look further.
`... and ...`	Both subtrees must agree.	and stops at the first false.

Watch it run. [2, 2, 2, 5, 2].

Watch out for:

Only comparing each node with its parent. That works too, but passing the root's value down is simpler.

LC 404 · Sum of Left Leaves

The problemReturn the sum of all leaves that are the left child of their parent.

What it doesPasses "am I a left child?" down; adds a leaf's value only when it is.

CostO(n).

The code. Information travels down as an argument and answers travel up as return values.

def sum_left_leaves(node, is_left=False):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return node.val if is_left else 0
    return sum_left_leaves(node.left, True) + sum_left_leaves(node.right, False)

function sumLeftLeaves(node: TreeNode | null, isLeft = false): number {
  if (node === null) {
    return 0;
  }
  if (node.left === null && node.right === null) {
    return isLeft ? node.val : 0;
  }
  return sumLeftLeaves(node.left, true) + sumLeftLeaves(node.right, false);
}

static int sumLeftLeaves(TreeNode node, boolean isLeft) {
    if (node == null) {
        return 0;
    }
    if (node.left == null && node.right == null) {
        return isLeft ? node.val : 0;
    }
    return sumLeftLeaves(node.left, true) + sumLeftLeaves(node.right, false);
}

Line by line.

Line	What it does	Why
`if node.left is None and node.right is None`	A leaf?	A leaf has no children at all.
`return node.val if is_left else 0`	Count it only if it hangs on the left.	The parent told us which side we are.
`sum_left_leaves(node.left, True)`	Tell the left child it's on the left.

Watch it run. [3, 9, 20, null, null, 15, 7]: the left leaves are 9 and 15.

Watch out for:

Counting the root when the tree is one node. A lone root isn't a left child: the answer is 0.

More practice, solved on the pattern pages

#	Problem	Level	Where
104	Maximum Depth of Binary Tree	Easy	Solved step by step on 10 · Binary Tree Traversal
226	Invert Binary Tree	Easy	Solved step by step on 10 · Binary Tree Traversal
100	Same Tree	Easy	Solved step by step on 10 · Binary Tree Traversal
101	Symmetric Tree	Easy	Solved step by step on 10 · Binary Tree Traversal
543	Diameter of Binary Tree	Easy	Solved step by step on 10 · Binary Tree Traversal
112	Path Sum	Easy	Solved step by step on 11 · Depth-First Search (DFS) on Graphs

8. Common mistakes

No base case for an empty nodeEvery recursive tree function must handle None first. Without it, node.left crashes on a missing child.

Mixing up height and depthDepth counts down from the root; height counts up from the leaves. Read which one the problem wants, and whether it counts nodes or edges.

Recomputing the same subtreeCalling height(node.left) twice per node can make an O(n) solution O(n²). Store results in variables.

Deep, unbalanced treesA tree shaped like a chain has height n; recursion that deep can overflow. An explicit stack avoids it.

Reading LeetCode lists as heap positionsChildren of a missing node are left out of the list. Build the tree properly (operation A).

9. Self-check quiz

What is a leaf?

Leaves are where every root-to-leaf path ends.

Given the heights of both subtrees, the height of the tree is…

One for this node, plus the deeper side.

How much stack does recursion on a tree use?

One frame per level on the current path: log n if balanced, n if a chain.

In [3, 9, 20, null, null, 15, 7], what is 20's left child?

9's children are the two nulls; then 20 receives 15 (left) and 7 (right).

10. Where it shows up next

10 · Binary Tree Traversal: preorder, inorder, postorder and level order, recursive and iterative.
11 · DFS: the same recursion on graphs, with a visited set.
14 · Backtracking: exploring a tree of choices.

Next structure: 10 · Binary search trees, trees with an ordering rule that makes searching fast.