Binary Trees and Recursion

A tree is a family

Picture a family tree, but upside down: one ancestor at the very top, their children below, and the children's children below them. In a binary tree, every "parent" has at most two children: a left one and a right one.

The key terms you'll hear in an interview:

• Node: a single element of the tree, holding a value and links to its children.
• Root: the topmost node. It has no parent.
• Leaf: a node with no children, the "end of a branch."
• Subtree: any node together with all its descendants. It's a full-fledged tree too.
• Height: the number of nodes on the longest path from the root to a leaf.

Look at the highlighted part. Node 3 with its children 1 and 6 looks like an ordinary little tree. All work with trees rests on this property: any tree is a root plus two subtrees, and each subtree is a tree too. The height of this tree is 3, for example along the path 8 → 3 → 1.

Height is sometimes counted in edges rather than nodes. Then the tree in the diagram has height 2. In an interview, ask which definition is meant. In "maximum depth" problems, nodes are usually what's counted.

What a node looks like in code

A node stores a value and two links to its children. If a child is missing, the link is empty: None, null, or nullptr.

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

How to think recursively: "trust the recursion"

Beginners often try to trace the recursion all the way down in their heads, juggling a dozen calls and getting lost. You don't need to do that.

Imagine you're a department head. You need to find out something about the whole tree. You don't walk through it yourself; you tell your two deputies: "You handle the left subtree, you handle the right one, and bring me the answer." Then you combine their answers with your own node. How the deputies get it done isn't your concern: they work exactly the way you do.

Every recursive function on a tree is built from three questions:

Question	What to answer
Base case	What do you return for an empty tree (null)?
Trust	Assume the function already works correctly for the left and right subtrees.
Combine	How do you get the answer for the whole tree from the two answers and the current node?

It's almost always convenient to make the empty node the base case, not the leaf. Then you don't have to handle "there's a left child but no right child" separately: empty branches take care of themselves.

Example: the height of a tree

Let's go through the three questions:

1. Base case: an empty tree has height 0.
2. Trust: height(left) and height(right) have already returned the correct subtree heights.
3. Combine: the tree's height is the height of the taller subtree plus one node, the current root. That gives 1 + max(left, right).

That's all the logic. Here's how it looks in code:

def height(root):
    if root is None:          # base case: empty tree
        return 0
    left = height(root.left)  # trust the recursion
    right = height(root.right)
    return 1 + max(left, right)  # combine the answer

Let's check it on our tree. The subtree rooted at 3 has height 2, and the subtree rooted at 10 also has height 2 (path 10 → 14). We get 1 + max(2, 2) = 3. It checks out.

Complexity

• Time is O(n): the function visits each node exactly once.
• Space is O(h), where h is the height of the tree. That's how many calls sit on the stack at once. For a balanced tree, h ≈ log n. For a degenerate tree that looks like a list, h = n.

How it sounds in an interview

"I'll solve it recursively. Base case: an empty node has height 0. Otherwise I compute the heights of the left and right subtrees and return the max plus one. I visit each node once, so that's O(n) time. Space is O(h) for the call stack, O(n) in the worst case for a chain-like tree."

Make a point of saying what h is and estimating the worst case. Interviewers appreciate that.

Common mistakes

• No base case, or a wrong one. Without a null check, the program crashes when it accesses root.left.
• Using the leaf as the base case instead of the empty node. The code sprouts checks like "what if there's only a left child?"
• Mixing up nodes and edges. That's where off-by-one answers come from. Agree on the definition up front.
• Forgetting the +1. Without it, the current node isn't counted, and the function always returns 0.
• Trying to track every call in your head. It's enough to check the base case and the combine step; the recursion does the rest.

This three-question template (base case, trust, combine) fits most tree problems: summing nodes, searching for a value, checking symmetry. In the practice ahead, you'll use it again and again, and it'll get faster with every problem.