Recognizing tree problems

A binary tree is like a linked list that branches: each node points to up to two children (left and right). That branching is the gateway to recursion — the tool that solves most of this section's problems almost on its own.

As always, every pattern lesson opens with a 🎯 Try it first.

The node: TreeNode

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

You keep only the root (root). From it, you go down through left/right until you hit None (a leaf has no children). Quick vocabulary: root (top), leaf (no children), height (h, the longest path from the root to a leaf), subtree (any node with its descendants).

In the lesson editor you use a real TreeNode. In the visualizations, we represent the tree with three arrays (values, left, right, with child indices) so we can draw it at every step — it is the same tree, left[i] is node.left.

Why recursion is the natural tool

The definition of a tree is recursive: a tree is a node whose children are... smaller trees. So almost every problem is solved with the same recipe:

Solve the problem for the children (recursion), then combine the results at the current node. The base case is the empty tree (None).

Instead of thinking about the whole tree at once, you trust that the recursion solves the subtrees and you only decide how to combine them. That shift in perspective is the heart of the section.

The three traversals (DFS)

Visiting all the nodes by "going deep" (DFS) has three orders, which differ in when you process the node relative to its children:

See the three on a hand-built tree:

Big-O in trees: O(n) and O(h)

Two measures that will show up all the time — and that you should always justify:

• Time O(n): traversing the tree visits each node once (n = number of nodes). Most tree algorithms are O(n).
• Space O(h): the recursion stacks one call per level it is diving into; at the bottom, the stack is as tall as the height h. Here lies the subtlety:
  • Balanced tree: h ≈ log n → space O(log n). 🎉
  • Degenerate tree (it becomes a "list", each node with a single child): h = n → space O(n). 😬

That is why "O(h)" is the honest way to state the recursion's space: it is great when the tree is balanced and bad when it is degenerate. Keep this distinction — it reappears in the BST (O(h) search) and justifies why balanced trees matter so much.

The section's problems

• Maximum Depth, Invert Tree, Same Tree → recursive DFS
• Level Order Traversal → level-order BFS
• Validate BST, Kth Smallest, Lowest Common Ancestor → BST properties
• Construct from Traversals, Serialize/Deserialize → construction
• Implement Trie → prefix tree

Summary

• Tree = nodes with left/right; you keep the root; a leaf has no children.
• Recursion is natural: solve the children, combine at the node, base case = None.
• DFS traversals: pre, in (ascending in a BST!) and postorder.
• O(n) time; O(h) space (log n if balanced, n if degenerate).

Next lesson: the recursive template that unlocks most trees.