Trees

What is a tree?

A tree is a connected, acyclic graph where each node has at most one parent and zero or more children. In interviews, "tree" almost always means binary tree - each node has at most two children named left and right:

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

A Binary Search Tree (BST) adds an ordering property: every node in the left subtree is strictly smaller than the current node, and every node in the right subtree is strictly larger. This holds recursively at every level, which makes search O(log n) on a balanced tree - each comparison eliminates half the remaining candidates.

The core trade-off: trees give hierarchical structure and O(log n) search/insert on a balanced BST, but random access by index is O(n) and balance is not guaranteed. A BST built by inserting already-sorted keys degenerates into a linked list (O(n) everything). Most binary tree interview problems do not require the BST property - they just need traversal. Always distinguish whether the BST ordering is in play before choosing your approach.

Core operations

Key patterns

Recursive DFS traversal

Walk the tree by recursing into each child, processing the current node before, between, or after those two calls.

When to use - the answer for a node depends on its subtrees: a height, a path sum, a yes/no property, or a rebuilt copy. The tree's own recursive shape hands you the structure for free, so you skip writing an explicit stack and managing it by hand.

How it works - the function solves the whole problem for one node by first solving it for root.left, then for root.right, then combining the two answers. The base case is root is None, which returns the identity value (0 for height, True for a property, None for a miss). Where you place the node's own work picks the ordering: preorder (node first) copies structure, inorder (node in the middle) visits a BST in sorted order, postorder (node last) lets the parent read both children's results. Each node is visited once, so the pass is O(n) time; the call stack goes O(h) deep, which is O(log n) when balanced and O(n) for a degenerate tree.

Level-order BFS traversal

Visit the tree one depth at a time, finishing every node on a level before touching the next.

When to use - the problem is phrased by level: minimum depth, the right-side view, a zigzag order, or anything that needs nodes grouped by how far they sit from the root. DFS reaches every node too, but it dives deep first and loses the layer boundaries, so you'd have to reconstruct them afterward.

How it works - keep a deque, enqueue the root, and loop while it holds anything. At the top of each pass, snapshot len(queue) - that count is exactly the number of nodes on the current level. Dequeue precisely that many, process each, and enqueue its non-null children behind them. The snapshot is what draws the line between levels: the children you add belong to the next level, and capturing the size first keeps them out of the current one. Every node is enqueued and dequeued once, so it runs in O(n) time, with O(w) space for the widest level.

Canonical examples

Maximum depth of a binary tree

A clean postorder recursion. The insight: the depth of a node is 1 plus the maximum depth of its deeper child. The base case (None) returns 0. This pattern - compute from children, return a value upward - is the template for the majority of binary tree problems.

Validate a BST

Not all tree problems are traversal. The BST check requires carrying bounds down through the tree: the left subtree must stay below the current node's value, and the right subtree must stay above it. Passing min_val and max_val through the recursion encodes this constraint without a global variable.

When to reach for a tree

• The problem describes a hierarchical relationship (file systems, org charts, nested structures).
• You need sorted operations with fast insert and delete - a balanced BST supports both in O(log n).
• The problem gives you a binary tree and asks about paths, depths, or subtree properties - recursive DFS.
• You need to process nodes level by level (minimum depth, right-side view, zigzag) - BFS with a queue.
• The problem involves expression parsing or evaluation - expression trees with postorder traversal.
• You need the k-th smallest or largest in a dynamic set - BST inorder yields sorted order.

Practice problems

• Maximum Depth of Binary Tree - Simplest postorder recursion.
• Invert Binary Tree - Preorder swap; confirms the recursive template.
• Same Tree - Structural equality via simultaneous DFS.
• Binary Tree Level Order Traversal - BFS with level grouping.
• Validate Binary Search Tree - Min/max bounds propagation.
• Lowest Common Ancestor of a Binary Search Tree - BST property to navigate to the split point.