Trees & Binary Search Trees: The Interview Favorite

Why Trees Are the Most-Tested Structure

If you rank interview topics by frequency at top tech companies, trees consistently lead the list. Not arrays, not graphs — trees.

The reason isn't that trees are the most commonly used data structure in production code. It's that tree problems test something interviewers care about deeply: recursive thinking. Can a candidate decompose a problem into a base case and a recursive case? Can they reason about what information needs to flow upward from children to parents, and what needs to flow downward from parents to children? Can they switch cleanly between thinking recursively and thinking iteratively?

These are questions about how someone thinks, not just what they know. That's why trees appear so frequently.

This post builds the recursive thinking framework first — then applies it to every major tree pattern you'll encounter.

The Node Structure

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

# Build a tree from a level-order list (LeetCode format)
# None represents missing nodes
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

The Recursive Thinking Framework

Every recursive tree function follows one of two information-flow patterns. Identifying which pattern a problem needs is the first step — before writing a single line of code.

Pattern A — Information flows UP (bottom-up): Children compute something and return it to the parent. The parent combines the children's results to produce its own result.

Examples: max depth, diameter, check if balanced, path sum from any node
Template:
  def solve(node):
      if not node: return BASE_CASE
      left_result  = solve(node.left)
      right_result = solve(node.right)
      return COMBINE(left_result, right_result, node.val)

Pattern B — Information flows DOWN (top-down): The parent passes state (accumulated sum, current path, target) to children. Children use it to make decisions or record results.

Examples: path sum root-to-leaf, all root-to-leaf paths, serialize tree
Template:
  def solve(node, state_from_parent):
      if not node: return
      new_state = UPDATE(state_from_parent, node.val)
      if IS_LEAF(node): RECORD(new_state)
      solve(node.left,  new_state)
      solve(node.right, new_state)

Every tree problem in this post fits one of these two templates. Once you identify which one applies, the code writes itself.

The Four Traversal Orders

All tree traversals are DFS variants — they differ only in when the current node is processed relative to its children.

# Pre-order: root → left → right
# Use for: serialization, copying a tree, prefix expression trees
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# In-order: left → root → right
# Use for: BST sorted output, validate BST, kth smallest in BST
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Post-order: left → right → root
# Use for: deleting a tree, evaluating expression trees, computing subtree sizes
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# Level-order (BFS): level by level, left to right
# Use for: minimum depth, right side view, connect level nodes, shortest path
from collections import deque
def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

Iterative in-order — useful when you need to avoid recursion stack overhead or when the problem requires stopping mid-traversal:

def inorder_iterative(root):
    result, stack = [], []
    current = root

    while current or stack:
        # Go as far left as possible
        while current:
            stack.append(current)
            current = current.left
        # Process node
        current = stack.pop()
        result.append(current.val)
        # Move to right subtree
        current = current.right

    return result

Technique 1: Depth, Height, and Balance

These are the foundational bottom-up problems. Master the pattern here and everything else in this section becomes a variation.

# Maximum depth (height) of binary tree — bottom-up
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# Minimum depth — note: different from max depth
# Minimum depth is the path to the NEAREST leaf, not just null
def min_depth(root):
    if not root:
        return 0
    if not root.left:
        return 1 + min_depth(root.right)   # only right subtree exists
    if not root.right:
        return 1 + min_depth(root.left)    # only left subtree exists
    return 1 + min(min_depth(root.left), min_depth(root.right))

# Check if balanced — O(n) single pass
def is_balanced(root):
    def check(node):
        if not node:
            return 0           # height of empty tree is 0
        left_h  = check(node.left)
        right_h = check(node.right)
        if left_h == -1 or right_h == -1:
            return -1          # propagate "unbalanced" signal upward
        if abs(left_h - right_h) > 1:
            return -1          # this subtree is unbalanced
        return 1 + max(left_h, right_h)

    return check(root) != -1

# Diameter — longest path between any two nodes (may not pass through root)
def diameter_of_binary_tree(root):
    max_diameter = [0]         # use list to allow mutation inside nested function

    def depth(node):
        if not node:
            return 0
        left_d  = depth(node.left)
        right_d = depth(node.right)
        max_diameter[0] = max(max_diameter[0], left_d + right_d)
        return 1 + max(left_d, right_d)

    depth(root)
    return max_diameter[0]

The diameter trap: Many candidates compute depth separately then combine — O(n²). The O(n) solution computes diameter and depth in a single pass, updating a global maximum during the bottom-up traversal.

Technique 2: Path Sum Problems

Path problems split into two categories — paths that must start at the root, and paths that can start anywhere.

# Root-to-leaf path sum — top-down (pass remaining target downward)
def has_path_sum(root, target_sum):
    if not root:
        return False
    remaining = target_sum - root.val
    if not root.left and not root.right:   # leaf node
        return remaining == 0
    return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)

# All root-to-leaf paths — top-down, collect path
def path_sum_all(root, target_sum):
    result = []
    def dfs(node, remaining, path):
        if not node:
            return
        path.append(node.val)
        remaining -= node.val
        if not node.left and not node.right and remaining == 0:
            result.append(list(path))     # record a valid path
        dfs(node.left,  remaining, path)
        dfs(node.right, remaining, path)
        path.pop()                        # backtrack
    dfs(root, target_sum, [])
    return result

# Path sum from ANY node to ANY node — bottom-up with global max
def max_path_sum(root):
    max_sum = [float('-inf')]

    def max_gain(node):
        if not node:
            return 0
        # Only take positive gains from children; negative = take 0 (skip branch)
        left_gain  = max(max_gain(node.left),  0)
        right_gain = max(max_gain(node.right), 0)

        # Price of the path passing through this node as the "top"
        price_here = node.val + left_gain + right_gain
        max_sum[0] = max(max_sum[0], price_here)

        # Return the max gain if we continue the path upward (can only go one direction)
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum[0]

The key distinction:

• Root-to-leaf paths → top-down (pass accumulated state)

• Any-node-to-any-node → bottom-up (return gain upward, track global max)

Technique 3: Lowest Common Ancestor (LCA)

LCA is a classic interview problem that tests whether you understand recursive return values.

# LCA in a general binary tree
def lowest_common_ancestor(root, p, q):
    if not root:
        return None
    if root == p or root == q:
        return root      # found one of the targets — return it upward

    left  = lowest_common_ancestor(root.left,  p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root      # p found in one subtree, q in the other → root is LCA
    return left or right # both in same subtree → return whichever was found

How to reason about it: Each call returns either None (neither p nor q is in this subtree), a node equal to p or q, or the LCA itself. The moment both left and right are non-null, the current node is the LCA — because that means p and q are in different subtrees, and this is the lowest node where they meet.

# LCA in a BST — use BST property for O(log n) instead of O(n)
def lca_bst(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left     # both smaller → go left
        elif p.val > root.val and q.val > root.val:
            root = root.right    # both larger → go right
        else:
            return root          # split point → this is the LCA

Technique 4: Tree Construction

Building a tree from traversal sequences tests whether you understand the relationship between traversal orders.

# Construct from pre-order and in-order traversals
def build_from_pre_in(preorder, inorder):
    if not preorder or not inorder:
        return None

    root_val = preorder[0]           # first element of preorder is always root
    root = TreeNode(root_val)
    mid  = inorder.index(root_val)   # find root in inorder

    # Left subtree: first mid elements of inorder, next mid elements of preorder
    root.left  = build_from_pre_in(preorder[1:mid+1], inorder[:mid])
    # Right subtree: remaining elements
    root.right = build_from_pre_in(preorder[mid+1:],  inorder[mid+1:])
    return root

# Optimized with index map — O(n) instead of O(n²)
def build_from_pre_in_fast(preorder, inorder):
    inorder_idx = {val: i for i, val in enumerate(inorder)}
    pre_idx = [0]

    def build(left, right):
        if left > right:
            return None
        root_val = preorder[pre_idx[0]]
        pre_idx[0] += 1
        root = TreeNode(root_val)
        mid  = inorder_idx[root_val]
        root.left  = build(left, mid - 1)
        root.right = build(mid + 1, right)
        return root

    return build(0, len(inorder) - 1)

The key insight: Pre-order always gives you the root first. In-order tells you which nodes are to the left and right of the root. These two pieces of information uniquely reconstruct the tree.

Serialize and Deserialize

def serialize(root):
    """Encode tree to string using pre-order DFS."""
    if not root:
        return 'N'
    return f"{root.val},{serialize(root.left)},{serialize(root.right)}"

def deserialize(data):
    """Decode string back to tree."""
    vals = iter(data.split(','))

    def build():
        val = next(vals)
        if val == 'N':
            return None
        node = TreeNode(int(val))
        node.left  = build()
        node.right = build()
        return node

    return build()

Technique 5: Binary Search Tree Operations

A BST has one defining property: for every node, all values in the left subtree are smaller, all values in the right subtree are larger. In-order traversal of a BST produces a sorted sequence.

# Validate BST — pass valid range downward
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if not (min_val < root.val < max_val):
        return False
    return (is_valid_bst(root.left,  min_val, root.val) and
            is_valid_bst(root.right, root.val, max_val))

# Kth smallest element — in-order traversal, stop at kth
def kth_smallest(root, k):
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Insert into BST
def insert_into_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left  = insert_into_bst(root.left,  val)
    else:
        root.right = insert_into_bst(root.right, val)
    return root

# Delete from BST — three cases
def delete_from_bst(root, key):
    if not root:
        return None
    if key < root.val:
        root.left  = delete_from_bst(root.left,  key)
    elif key > root.val:
        root.right = delete_from_bst(root.right, key)
    else:
        # Case 1: leaf node
        if not root.left and not root.right:
            return None
        # Case 2: one child
        if not root.left:  return root.right
        if not root.right: return root.left
        # Case 3: two children — replace with in-order successor
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val   = successor.val
        root.right = delete_from_bst(root.right, successor.val)
    return root

BST validation trap: The most common mistake is comparing only with the immediate parent. This misses violations like:

    5
   / \
  1   4      ← 4 < 5, seems ok locally
     / \
    3   6    ← but 3 < 5, which violates BST property for the right subtree

The correct approach: pass a valid range (min_val, max_val) down the tree.

Technique 6: Views and Boundaries

Right side view, left side view, and vertical traversals — all solved with BFS or DFS plus level tracking.

# Right side view — last node at each BFS level
def right_side_view(root):
    if not root:
        return []
    result = []
    queue  = deque([root])

    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:        # last node at this level
                result.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)

    return result

# Left side view — first node at each BFS level
def left_side_view(root):
    if not root:
        return []
    result = []
    queue  = deque([root])

    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == 0:                     # first node at this level
                result.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)

    return result

The Decision Framework

Tree problem received
         │
         ▼
Does the answer depend on VALUES ACCUMULATED along a path from root?
  └─ Yes → TOP-DOWN DFS (pass state as parameter)
         │
         ▼
Does the answer depend on COMBINING results from left and right subtrees?
  └─ Yes → BOTTOM-UP DFS (return value upward)
         │
         ▼
Does the problem need LEVEL-BY-LEVEL processing or SHORTEST PATH in tree?
  └─ Yes → BFS with deque
         │
         ▼
Is it a BST problem?
  ├─ "Validate" → pass (min, max) range downward
  ├─ "Kth smallest/largest" → in-order traversal (iterative, stop at k)
  └─ "Search/insert/delete" → follow BST property left/right
         │
         ▼
Does the problem involve a PATH that can go through any node?
  └─ Yes → BOTTOM-UP, track global max, return single-direction gain
         │
         ▼
Need to FIND TWO NODES (LCA, distance between nodes)?
  └─ Yes → recursive LCA pattern (return found nodes upward)

The 10 Must-Know Tree Problems

Problems 1–4: get the recursive framework solid. Problems 5–9: each applies a different aspect of the framework. Problem 10 is the capstone — it requires combining bottom-up thinking with a non-obvious "only take positive gains" insight.

Bottom Line

Tree problems don't test whether you've memorized tree algorithms. They test whether you've internalized recursive thinking. The two templates — top-down and bottom-up — are the entire framework. Every tree problem you'll encounter maps to one of them, or a combination of both.

Build that instinct. Before writing any tree function, ask: "Does information flow down from parent to children, or up from children to parent?" Answer that question, and the function signature and base case will follow naturally.

🧭 What's Next in This Series

One post remains in Chapter 2:

• Post 09 (Final — Chapter 2): Graphs — BFS, DFS, topological sort, union-find, and grid traversal, with the decision framework that maps any graph problem to the right algorithm in 30 seconds