Binary Trees: 8 Practice Problems with Solutions

The fastest way to get fluent with trees is to grind through a focused set of canonical problems. Each problem below is short, but the pattern it teaches recurs across dozens of variants. Read the prompt, try it yourself, then compare with the solution.

We’ll use this TreeNode throughout:

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

Problem 1: Maximum Depth of a Binary Tree

Problem. Given the root of a binary tree, return its maximum depth — the number of nodes on the longest root-to-leaf path.

Example.

     3
    / \
   9  20
      / \
     15  7

Answer: 3.

Approach. Pure postorder recursion. Depth of None is 0; otherwise 1 + max(left_depth, right_depth).

def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

t = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(max_depth(t))    # 3

Time O(n), space O(h) for the recursion stack.

Problem 2: Same Tree

Problem. Given the roots of two binary trees, return True if they have the same structure and the same values at every node.

Example.

   1        1
  / \      / \
 2   3    2   3   -> True

   1        1
  /          \
 2            2   -> False (different shape)

Approach. Recurse on both trees in lockstep. They’re the same if both are None, or both exist with equal values and matching subtrees.

def same_tree(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if p.value != q.value:
        return False
    return same_tree(p.left, q.left) and same_tree(p.right, q.right)

Time O(n), space O(h).

Problem 3: Invert a Binary Tree

Problem. Given the root of a binary tree, invert it — swap the left and right children of every node — and return the new root.

Example.

     4               4
    / \             / \
   2   7    ->     7   2
  / \ / \         / \ / \
 1  3 6  9       9  6 3  1

Approach. Recurse, then swap.

def invert(root):
    if root is None:
        return None
    root.left, root.right = invert(root.right), invert(root.left)
    return root

Notice the simultaneous assignment — it swaps and recurses in one expression. This is the famous “homework problem” tweet from a few years back; it really is this short.

Problem 4: Symmetric Tree

Problem. Given the root of a binary tree, return True if it is a mirror of itself around its center.

Example.

     1
    / \
   2   2
  / \ / \
 3  4 4  3   -> True

Approach. A tree is symmetric if the left subtree mirrors the right subtree. Two subtrees mirror each other if their roots are equal and left.left mirrors right.right while left.right mirrors right.left.

def is_symmetric(root):
    def mirror(a, b):
        if a is None and b is None:
            return True
        if a is None or b is None:
            return False
        if a.value != b.value:
            return False
        return mirror(a.left, b.right) and mirror(a.right, b.left)

    if root is None:
        return True
    return mirror(root.left, root.right)

Time O(n), space O(h).

Problem 5: Path Sum

Problem. Given the root of a binary tree and an integer target, return True if there exists a root-to-leaf path whose values sum to target.

Example.

      5
     / \
    4   8
   /   / \
  11  13  4
 / \       \
7   2       1

target = 22 -> True   (5 -> 4 -> 11 -> 2)

Approach. Recurse, subtracting the current node’s value from the remaining target. Return True at a leaf when the remaining target hits zero.

def has_path_sum(root, target):
    if root is None:
        return False
    # leaf check
    if root.left is None and root.right is None:
        return root.value == target
    remaining = target - root.value
    return (has_path_sum(root.left, remaining)
            or has_path_sum(root.right, remaining))

The subtle bit: the sum check happens at the leaf, not at None. Treating a missing child as a “path of sum 0” would incorrectly accept partial paths from non-leaves.

Time O(n), space O(h).

Problem 6: Lowest Common Ancestor (LCA)

Problem. Given the root of a binary tree and two distinct nodes p and q known to exist in it, return their lowest common ancestor — the deepest node that has both p and q in its subtree (a node can be its own ancestor).

Example.

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

LCA(5, 1) = 3
LCA(5, 4) = 5

Approach. Recurse. If the current node is p, q, or None, return it. Otherwise recurse into both children. If both calls return non-None, the current node is the split point — the LCA. Otherwise return whichever side returned a non-None.

def lca(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root
    return left if left else right

It’s almost suspiciously short — but every case is covered. Time O(n), space O(h).

Problem 7: Validate a Binary Search Tree

Problem. Given the root of a binary tree, return True if it is a valid BST: for every node, all values in its left subtree are strictly less, and all values in its right subtree are strictly greater.

Example.

   2
  / \
 1   3       -> True

   5
  / \
 1   4
    / \
   3   6    -> False (3 is in the right subtree of 5 but less than 5)

Approach. The classic mistake is to check only that left.value < node.value < right.value. That allows the broken example above. Instead, pass down bounds: each node must lie strictly between low and high. Initially the bounds are (-inf, inf).

def is_valid_bst(root):
    def check(node, low, high):
        if node is None:
            return True
        if not (low < node.value < high):
            return False
        return (check(node.left, low, node.value)
                and check(node.right, node.value, high))
    return check(root, float("-inf"), float("inf"))

The bounds tighten as you descend: going left tightens the upper bound; going right tightens the lower bound. Time O(n), space O(h).

An alternative is the inorder approach from the previous post — both are valid; bounds is usually more flexible if duplicates have special rules.

Problem 8: Serialize and Deserialize a Binary Tree

Problem. Design an algorithm to convert a binary tree to a string and back. The serialized form must round-trip — deserialize(serialize(tree)) returns the same tree.

Approach. Preorder traversal, using a sentinel (#) for None. Deserialization consumes tokens from an iterator.

def serialize(root):
    out = []
    def go(node):
        if node is None:
            out.append("#")
            return
        out.append(str(node.value))
        go(node.left)
        go(node.right)
    go(root)
    return " ".join(out)

def deserialize(data):
    tokens = iter(data.split())
    def go():
        tok = next(tokens)
        if tok == "#":
            return None
        node = TreeNode(int(tok))
        node.left = go()
        node.right = go()
        return node
    return go()

t = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
s = serialize(t)
print(s)                    # 1 2 # # 3 4 # # 5 # #
t2 = deserialize(s)
print(serialize(t2) == s)   # True

The # placeholders are what make the round-trip lossless. Without them you couldn’t tell where a subtree ends.

Time O(n) for both directions; the serialized string is O(n) characters.

Patterns to take away

Stepping back across all eight, a few patterns repeat:

• Recurse on both children, combine results. Max depth, same tree, invert, symmetric, path sum, LCA — all variations on f(left); f(right); combine.
• Pass extra state down. Validate BST passes (low, high); path sum passes the remaining target. When a node’s correctness depends on its ancestors, the recursion needs to carry that context.
• Use None as a base case. Most tree recursions terminate on None. A handful (path sum, leaf-aware traversals) need a leaf base case instead.
• Inorder for sorted output. Preorder for serializing top-down. Postorder for aggregates and resource cleanup. Level-order for breadth-first questions.

Once these click, most “new” tree problems are really old problems wearing a new prompt.

Quick complexity table

Problem	Time	Space
Max depth	O(n)	O(h)
Same tree	O(n)	O(h)
Invert	O(n)	O(h)
Symmetric	O(n)	O(h)
Path sum	O(n)	O(h)
LCA	O(n)	O(h)
Validate BST	O(n)	O(h)
Serialize/deserialize	O(n)	O(n)

h is the tree’s height — O(log n) for balanced trees, O(n) for skewed.

Recap

You now have clean Python solutions for the eight most-asked tree problems. The big ideas:

• Recurse on both children and combine — this is the spine of every solution
• Pass bounds or remaining targets down when the answer depends on ancestors
• Choose the traversal that matches the problem’s natural direction
• Watch out for the BST validation trap — local comparisons are not enough
• Use placeholder tokens for serialization so the structure round-trips

Next steps

Trees are a special case of a more general structure — graphs. The next post introduces graphs, their representations (adjacency list, adjacency matrix, edge list), and the trade-offs between them. After that, BFS and DFS become tools you can apply to anything connected by edges.

→ Next: Graphs Introduction and Representations

Questions or feedback? Email codeloomdevv@gmail.com.