Skip to content

Binary Trees

Lesson 2 of 7 in Recursion, Trees & Graphs · 40 min · Intermediate

Each node has up to two children; problems split in half.

Introduction

A company's org chart has the CEO on top, managers under her, and teams under them. How do you print everyone level by level (the CEO, then all her direct reports, then their reports) when each person only knows their own direct reports?

Nobody holds the whole chart. Each person knows one thing: who reports to them, at most two people in this chart. You can start at the CEO and ask her.

You could follow one manager all the way down to the newest hire, then come back up for the next branch. That visits everyone, but not level by level. What do you keep track of instead?

Lesson overview

This lesson will show you how to:

  • Explain why a tree function usually starts with a null-node base case.
  • Trace pre-order, in-order and post-order traversals of a binary tree.
  • Use a queue to walk a tree level by level.
  • Compute maximum depth by combining the answers from both subtrees.
  • Spot a chain-shaped tree, where every node has only one child.
  • Invert a binary tree by swapping children at every node.

The picture

3920157rootroot: no parentparent of 15 and 7leaf: no childrenBinary tree with 5 nodes. Root 3. 3's children 9 and 20; 20's children 15 and 7. Pointers: root at 3.

Mental model

Picture a family tree drawn upside down, or a tournament bracket. One winner sits at the top, and every match below it has exactly two feeder matches. That is a binary tree: the root at the top, each node with a left and a right child, and the leaves at the bottom.

You only hold the root. To reach anyone else you walk down from it, left or right, one step at a time.

Every node is the root of its own smaller tree, so a question about the whole tree is the same question asked of the left child and the right child.

Words to know

root
The top node. It has no parent, and it is the only node you hold on to.
leaf
A node with no children: both its left and its right are null.
parent / child
A node points down to its children, and each child has exactly one parent. In a binary tree a node has at most two: left and right.
subtree
A node together with everything below it. Every subtree of a tree is itself a tree, which is why recursion fits.
depth vs height
Depth is how far a node is from the root (the root is 0). Height is how far the longest path goes down from a node. LeetCode's "maximum depth" counts nodes on the longest root-to-leaf path, so a single node has maximum depth 1.
pre-, in-, post-order
The three depth-first orders. They differ only in when a node is written: before its two subtrees (pre), between them (in) or after them (post).
level-order
Visit the root, then its children, then their children, level by level. It uses a queue, not recursion.
null child
A missing left or right child (None in Python, nullptr in C++). Recursive tree code stops when it reaches one.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: The problem hands you the root of a binary tree (a TreeNode) and asks about the whole tree.
  • Yes: The data is a hierarchy: folders, an org chart, a family tree, a bracket.
  • Yes: You can write the answer for a node using the answers of its left and right child.
  • Yes: It says level by level, right side view or depth: a queue, or a depth-first walk.

Not this when

  • No: Values must stay sorted so you can look them up fast: that is a binary search tree, a tree plus an ordering rule.
  • No: You always need the smallest or largest item next: that is a heap, which is also drawn as a tree.
  • No: Things can loop back, like a network or a grid: a node can be reached two ways, so you need a visited set. That is graph work. A tree has exactly one path between two nodes, so BFS on a tree gives levels, not shortest paths.

Which pattern fits?

  1. Which pattern? 1 of 5

    Given the root of a binary tree, return the number of nodes on the longest path from the root down to a leaf.

  2. Which pattern? 2 of 5

    Given the root of a binary search tree, return the k-th smallest value in it.

  3. Which pattern? 3 of 5

    List every string of n pairs of parentheses that is correctly matched.

  4. Which pattern? 4 of 5

    Given the root of a binary tree, return its node values level by level, from left to right.

  5. Which pattern? 5 of 5

    A grid of 1s (land) and 0s (water) is given. Count the islands.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1out = []; dfs(root)
  2. dfs(node):
  3. 2if node is null: return
  4. 3pre-order: write node.value here
  5. 4dfs(node.left)
  6. 3in-order: write node.value here
  7. 5dfs(node.right)
  8. 3post-order: write node.value here
  9. 6return to the caller
  10. 7return out

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

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


def dfs(node, order, out):
    if node is None:
        return
    if order == "pre": out.append(node.val)
    dfs(node.left, order, out)
    if order == "in": out.append(node.val)
    dfs(node.right, order, out)
    if order == "post": out.append(node.val)
    return


def dfs_order(root, order):
    out = []
    dfs(root, order, out)
    return out
Time · O(n)Space · O(h)
  • Each node is entered once and written once, so every traversal, depth-first or level by level, is O(n) time.
  • The recursion uses a call stack as deep as the tree is tall: O(h). That is about log n for a balanced tree and n for a chain. Level-order instead holds up to one whole level in its queue, which is O(width).
  • Pick one of the three write lines. Where it sits is the whole difference between pre-order, in-order and post-order.
  • Start every tree function with the null check. It covers the empty tree and the bottom of every branch in one line.
  • A lot of tree answers are post-order: ask both children, then combine, like 1 + max(left, right) for depth.
  • Level-order: copy len(queue) into size before the inner loop, because the queue grows while you add children. Put the root in only if it is not null.
  • Python's default recursion limit is about 1000, so a very tall tree may need an iterative version.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Given the root of a binary tree, return its maximum depth: the number of nodes along the longest path from the root down to the farthest leaf.

Input

root = [3,9,20,null,null,15,7]

Output

3

Approach

  1. An empty tree has depth 0. That is the base case.
  2. Ask the left child how deep its side is, then ask the right child.
  3. This node adds itself: return 1 + max(left, right).
  4. A leaf asks two null sides, gets 0 and 0, and returns 1.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


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


def max_depth(root):
    return depth(root)
Time · O(n)Space · O(h)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. Why does a recursive tree function usually begin with "if node is null: return"?
  2. What is the in-order traversal of the tree [3, 9, 20, null, null, 15, 7]?
  3. A tree of n nodes is one long chain, every node having only a left child. How deep does the recursive call stack get?
  4. In level-order, why do you copy size = len(queue) before the inner loop?
  5. The left subtree of a node has maximum depth 4 and the right subtree has maximum depth 2. What does max_depth return for that node?

Question 1 of 5

Why does a recursive tree function usually begin with "if node is null: return"?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Same Tree (opens in a new tab) (LeetCode, easy)

    Hint: Walk both trees at the same time: two nulls match, one null doesn't, and the values and both sides must agree.

  2. Solve Symmetric Tree (opens in a new tab) (LeetCode, easy)

    Hint: Compare the left subtree against the right one as a mirror: the outer children meet each other, and so do the inner ones.

  3. Solve Path Sum (opens in a new tab) (LeetCode, easy)

    Hint: Take this node's value off the target as you go down, and check what is left only when you stand on a leaf.

  4. Solve Diameter of Binary Tree (opens in a new tab) (LeetCode, easy)

    Hint: The longest path through a node is its left height plus its right height. Return the height upward, and keep the best path in a separate variable.

  5. Solve Lowest Common Ancestor of a Binary Tree (opens in a new tab) (LeetCode, medium)

    Hint: Ask each side whether it contains p or q. The first node that hears yes from both sides, or is p or q itself, is the answer.

  6. Solve Binary Tree Right Side View (opens in a new tab) (LeetCode, medium)

    Hint: What you can see from the right is the last node of each level. A level-order walk already knows where each level ends.

  7. Solve Construct Binary Tree from Preorder and Inorder Traversal (opens in a new tab) (LeetCode, medium)

    Hint: The first preorder value is the root. Find it in the inorder list to learn how many nodes go left, then build each side from its slice.

  8. Solve Binary Tree Maximum Path Sum (opens in a new tab) (LeetCode, hard)

    Hint: Like the diameter, but with values: return the best one-sided path to the parent, and record the best bent path through a node. Ignore a side that sums below 0.

Additional resources