Trees & Binary Search Trees

A tree is a graph with hierarchy: one root, child links, and no cycles. That shape makes many problems feel almost too simple once you trust recursion. Solve the left subtree, solve the right subtree, then combine the two answers at the current node.

Binary search trees add ordering. Every value in the left subtree is smaller than the node, and every value in the right subtree is larger. That one invariant turns search, insertion, and validation into guided walks instead of blind traversals.

The mental model

A binary tree node stores a value and up to two child references:

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

Most tree code has the same recursive shape:

def solve(node):
    if node is None:
        return base_answer

    left = solve(node.left)
    right = solve(node.right)
    return combine(node.val, left, right)

Traversal is the order in which you visit nodes:

• Preorder — node, left, right. Useful when the parent should be processed before children, like copying or serializing a tree.
• Inorder — left, node, right. In a BST, this produces values in sorted order.
• Postorder — left, right, node. Useful when the parent depends on child answers, like deleting or computing subtree sizes.
• Level-order — breadth-first by depth, using a queue.

from collections import deque


def inorder(node):
    if not node:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)


def level_order(root):
    if not root:
        return []
    out = []
    q = deque([root])
    while q:
        node = q.popleft()
        out.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return out

For BSTs, the invariant is global, not just parent-child. Every node in the entire left subtree must be below the current value; every node in the entire right subtree must be above it. That is why bounds are safer than only comparing a node with its immediate children.

Pattern recognition

Variations

Worked problems

The first two problems are traversal mechanics. The third is the BST invariant in its most interview-relevant form.

def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

from collections import deque


def level_order(root):
    if root is None:
        return []

    ans = []
    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)
        ans.append(level)
    return ans

def is_valid_bst(root):
    def valid(node, low, high):
        if node is None:
            return True
        if not (low < node.val < high):
            return False
        return valid(node.left, low, node.val) and valid(node.right, node.val, high)

    return valid(root, float("-inf"), float("inf"))

The classic pitfall