Overview

A binary tree is a set of nodes where each node has at most two children. Trees model hierarchies — file systems, organisation charts, parsed expressions — and they are the most common interview topic after arrays. Nearly every tree problem is solved by visiting each node once, so the real question is in what order and carrying what information.

Think of each recursive call as asking a subtree a question. Top-down solutions pass information down (the depth so far, the allowed range). Bottom-up solutions ask each child for an answer and combine them (the height of a subtree, whether it is balanced). Breadth-first traversal with a queue handles anything phrased in terms of levels.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Any traversalO(n) time
Recursion stackO(h): O(log n) balanced, O(n) skewed
BFS queueO(w) where w is the maximum width

Patterns to recognise

Return from children

Use it for: Max depth, diameter, balanced tree, max path sum.

Compute left and right results, combine, and update a global best if needed.

Carry state down

Use it for: Path sum, good nodes, sum root-to-leaf numbers.

Add the current node to the state before recursing into children.

Level order

Use it for: Right side view, average of levels, zigzag traversal.

BFS, processing len(queue) nodes per level.

Code template

Max depth (DFS) and level order (BFS)
from collections import deque


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


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


def level_order(root):
    if not root:
        return []
    levels, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels

Common mistakes

  • Forgetting the null case — every recursive tree function needs it first.
  • Confusing depth and height, or counting edges vs nodes; read the definition in the problem.
  • A global "best" variable must be reset between test cases.
  • Deep, skewed trees can overflow the recursion stack — iterate with an explicit stack if n is large.

Quick check

Three questions on Binary Trees. Get all three right to earn +15 XP.

  1. Inorder traversal visits nodes in which order?

  2. A recursive DFS on a tree with n nodes and height h uses how much stack space?

  3. Level-order traversal of a binary tree is implemented with:

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Binary Trees?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor