Patterns

Trees

A tree in this kind of interview is a set of nodes with a parent and children, usually a binary tree: each node has a left child, a right child, or neither. There is no cycle. If you are not sure the structure is a tree, you are in graph territory, and the graphs page adds visited-sets for that reason. Cycles are the difference that causes infinite recursion.

Most tree tasks are a walk plus a rule for combining the answers from the children. The walk is either depth-first, which follows one child all the way down before the other, or breadth-first, which finishes a whole level before the next. Pick the walk from the question you were asked. "How tall is the tree?" can be depth-first. "What is on level 3?" wants breadth-first, or a depth-first search that also tracks depth. Either can be correct. The clumsy version is to memorize four traversal names and not know what they return.

A node and a depth-first height

Height here means the number of edges on the longest path from the node down to a leaf. An empty tree has no edges. This page treats the height of an empty tree as -1 and the height of a single node as 0, and it says so. Other definitions count nodes instead of edges. The prompt decides. Write the choice in the docstring or in a comment before you code, because this is a favorite off-by-one.

from collections import deque


class Node:
    def __init__(self, value: int, left: "Node | None" = None, right: "Node | None" = None):
        self.value = value
        self.left = left
        self.right = right


def height(node: Node | None) -> int:
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))


single = Node(1)
assert height(None) == -1
assert height(single) == 0
assert height(Node(1, Node(2), Node(3, Node(4)))) == 2

Each node is visited once. At each node you do a constant amount of work besides the recursive calls. Time is linear in the number of nodes. The extra space is the call stack, which is proportional to the height. A balanced tree uses logarithmic stack space. A completely skewed tree uses linear stack space. Say both. "The recursion is O(log n)" is only true for the balanced shape, and the prompt may not promise balance.

The empty child is the base case. Forgetting it is how you get an attribute error on None.left rather than a wrong number. The common mistakes page treats that as a representative tree bug: the algorithm was fine, and the base case was imaginary.

Searching with the same walk

Finding a value is the same walk with a different combination rule. Ask the left subtree. If it says yes, you are done. Otherwise ask the right. An empty node says no.

def contains(node: Node | None, target: int) -> bool:
    if node is None:
        return False
    if node.value == target:
        return True
    return contains(node.left, target) or contains(node.right, target)


root = Node(1, Node(2), Node(3, Node(4)))
assert contains(root, 4) is True
assert contains(root, 9) is False

This is correct for any binary tree. It is not taking advantage of binary-search-tree order. If the prompt promises that every left descendant is smaller and every right descendant is larger, you can skip one side, and the binary search idea comes back in tree clothing. Do not skip a side unless that promise was made. A lot of wrong tree code is a binary search written on a tree that was never sorted.

Time is still linear in the worst case, because the value might be absent and you might have to look at every node. In a balanced binary search tree the expected successful search is logarithmic. Quote the version that matches the promise you were given, not the version you wish you had.

Breadth-first levels

Level order is the queue policy from the stacks and queues page. You start with the root in the queue. While the queue is not empty, you take the front node, record it, and push its existing children. Children are pushed in the order you want them visited, usually left then right.

def level_values(node: Node | None) -> list[int]:
    if node is None:
        return []
    queue = deque([node])
    values: list[int] = []
    while queue:
        current = queue.popleft()
        values.append(current.value)
        if current.left is not None:
            queue.append(current.left)
        if current.right is not None:
            queue.append(current.right)
    return values


assert level_values(Node(1, Node(2), Node(3, Node(4)))) == [1, 2, 3, 4]
assert level_values(None) == []

Each node enters the queue once and leaves once. Time is linear. Extra space is proportional to the widest level, which can be about half the nodes in a complete tree, so you should call it linear in the worst case. Do not use a Python list and pop(0) here. That would make each pop cost linear time and the whole walk quadratic. deque is the point of importing it.

If the task asks for values grouped by level, take a snapshot of the queue length at the start of each level and loop that many times before you call the inner loop a new level. The snapshot is the whole trick. If you loop while queue without the snapshot, you will mix the next level into the current one as you append children. Try that bug on purpose once so you recognize it.

What to say, and how to practice

Say whether the structure is a tree or might contain a cycle. Say whether you are going depth-first or level by level, and why. Say the base case out loud: "an empty child returns -1" or "an empty child returns false." Then give time and the extra space, including the shape of the recursion stack.

Practice on a tree you draw before you code. Three nodes is enough to catch a swapped left and right. Add a fourth node on one side so the height assert is not symmetric. Implement height and level_values from a blank file. Then write sum_of_values by copying the shape of height and replacing max with addition. If that feels mechanical, good. Tree problems get easier when the walk stays stable and only the combination rule changes.

When the combination rule needs information from both children before it can answer, you are still in the same pattern. Balanced-tree checks, for example, need the height of each side and a boolean. Return a small pair from the helper instead of computing the height twice with two full walks. One walk, a richer return value. That refactor is worth doing on paper even if you never get that specific question.