readyforhires
Sign up free

Binary Trees 101

Intermediate · 4 chapters · 8 min read · Think recursively: solve the tree by trusting the answer from each subtree.

Practise this in the app All guides

Trees and the recursive mindset

What a binary tree is

A binary tree is a set of nodes where each node has a value and up to two children, left and right. The top node is the root; nodes without children are leaves. The height is the number of edges (or nodes, depending on the definition — clarify) on the longest root-to-leaf path. A balanced tree with n nodes has height about log n; a skewed one can have height n.

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

A binary search tree (BST) adds an ordering rule: every value in the left subtree is smaller than the node, every value in the right subtree is larger. An in-order traversal of a BST visits values in sorted order, which solves many BST questions directly.

Signals in a problem statement

The recursive mindset

Most tree solutions follow one shape: ask each child for its answer, combine with the current node, return. You do not trace the whole recursion in your head. You trust that depth(node.left) returns the correct depth, and only reason about one node. The base case is almost always if node is None. If you can say "a node's answer is f(left answer, right answer, node value)", the code is three lines.

Core patterns with templates

1. Bottom-up: combine children's answers

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

def invert(node):
    if node:
        node.left, node.right = invert(node.right), invert(node.left)
    return node

2. Compare two subtrees together

def is_symmetric(root):
    def mirror(a, b):
        if not a or not b:
            return a is b
        return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)
    return mirror(root, root)

3. Top-down: pass constraints downward

def is_valid_bst(node, lo=float("-inf"), hi=float("inf")):
    if not node:
        return True
    if not lo < node.val < hi:
        return False
    return is_valid_bst(node.left, lo, node.val) and is_valid_bst(node.right, node.val, hi)

Checking only a node against its direct children is the classic wrong answer; the bounds carry the whole ancestry.

4. Level-order traversal (BFS)

from collections import deque

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

5. Return one thing, track another

For the maximum path sum, each call returns the best downward path from the node, while a shared variable records the best path that bends through the node.

def max_path_sum(root):
    best = float("-inf")
    def down(node):
        nonlocal best
        if not node:
            return 0
        l = max(down(node.left), 0)
        r = max(down(node.right), 0)
        best = max(best, node.val + l + r)
        return node.val + max(l, r)
    down(root)
    return best

Complexity, mistakes and edge cases

Complexity

TaskTimeSpace
Any full traversal (DFS or BFS)O(n)O(h) recursion or O(w) queue
BST search / insertO(h)O(1) iterative
k-th smallest via in-orderO(h + k)O(h)
Build from preorder + inorder (with index map)O(n)O(n)

Here h is the height and w the maximum width. For a balanced tree h ≈ log n; for a skewed tree h = n, so recursion depth can reach 10⁵ and break Python's default limit. Mention sys.setrecursionlimit or an explicit stack if the constraints are large.

Common mistakes

Edge cases

Empty tree, single node, only left children (a linked list in disguise), complete tree, all equal values, negative values, very deep trees.

Iterative in-order traversal

def kth_smallest(root, k):
    st, node = [], root
    while st or node:
        while node:
            st.append(node)
            node = node.left
        node = st.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

Being able to write this without recursion is a common follow-up.

Variations and practise

How interviewers twist it

How to explain it

State the recursive contract: "down(node) returns the best path that starts at node and goes down; I update the global best with the path that bends at node." With that sentence, the interviewer can follow every line you write.

Practise

The problems below move from depth, inversion and symmetry, through level-order traversal and BST validation, to the k-th smallest element, building a tree from two traversals, and the maximum path sum. Write the recursive contract as a comment before each solution.

Practise

Easy

Medium

Hard

Practise this in the app All guides