Binary trees, BSTs, traversals, and the recursive patterns that dominate tree interview problems

Trees

Trees are the most common recursive data structure in interviews. The good news: tree problems have a small number of patterns, and once you internalize them, most problems become variations.

Binary Tree Basics

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

Key properties:

Height: Longest path from root to leaf. Balanced tree: O(log n). Skewed tree: O(n).
Depth: Distance from root to a node.
Full binary tree: Every node has 0 or 2 children.
Complete binary tree: All levels filled except possibly the last, filled left to right. This is what heaps use.
Balanced binary tree: Height difference between left and right subtrees is at most 1 for every node.

Traversals

The four traversals every engineer must know cold:

Recursive Traversals

// In-order: left -> root -> right (gives sorted order for BST)
function inorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [...inorder(root.left), root.val, ...inorder(root.right)];
}

// Pre-order: root -> left -> right (useful for serialization)
function preorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [root.val, ...preorder(root.left), ...preorder(root.right)];
}

// Post-order: left -> right -> root (useful for deletion, calculating sizes)
function postorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [...postorder(root.left), ...postorder(root.right), root.val];
}

Iterative In-Order (Important for Interviews)

function inorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let current = root;

  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop()!;
    result.push(current.val);
    current = current.right;
  }

  return result;
}

Level-Order (BFS)

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

Binary Search Tree (BST)

BST property: For every node, all values in the left subtree are less, all values in the right subtree are greater.

function searchBST(root: TreeNode | null, target: number): TreeNode | null {
  if (!root) return null;
  if (target === root.val) return root;
  if (target < root.val) return searchBST(root.left, target);
  return searchBST(root.right, target);
}

function insertBST(root: TreeNode | null, val: number): TreeNode {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insertBST(root.left, val);
  else root.right = insertBST(root.right, val);
  return root;
}

Validate BST -- a common trap: you must pass bounds, not just compare parent and child.

function isValidBST(
  root: TreeNode | null,
  min = -Infinity,
  max = Infinity
): boolean {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return (
    isValidBST(root.left, min, root.val) &&
    isValidBST(root.right, root.val, max)
  );
}

Common Interview Patterns

Maximum Depth

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Diameter of Binary Tree

Longest path between any two nodes. May or may not pass through the root.

function diameterOfBinaryTree(root: TreeNode | null): number {
  let diameter = 0;

  function height(node: TreeNode | null): number {
    if (!node) return 0;
    const left = height(node.left);
    const right = height(node.right);
    diameter = Math.max(diameter, left + right);
    return 1 + Math.max(left, right);
  }

  height(root);
  return diameter;
}

Lowest Common Ancestor (LCA)

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  if (!root || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root;   // p and q are on different sides
  return left ?? right;              // both on the same side
}

Path Sum

function hasPathSum(root: TreeNode | null, target: number): boolean {
  if (!root) return false;
  if (!root.left && !root.right) return root.val === target;
  return (
    hasPathSum(root.left, target - root.val) ||
    hasPathSum(root.right, target - root.val)
  );
}

Serialize / Deserialize

function serialize(root: TreeNode | null): string {
  if (!root) return 'null';
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

function deserialize(data: string): TreeNode | null {
  const values = data.split(',');
  let index = 0;

  function build(): TreeNode | null {
    if (values[index] === 'null') {
      index++;
      return null;
    }
    const node = new TreeNode(Number(values[index++]));
    node.left = build();
    node.right = build();
    return node;
  }

  return build();
}

Balanced Trees (Overview)

You rarely need to implement these in interviews, but you should know what they do:

AVL Tree: Strictly balanced (height difference <= 1). Rotations on every insert/delete. Faster lookups than Red-Black but slower writes.

Red-Black Tree: Relaxed balance. Used by Java TreeMap, C++ std::map. Guarantees O(log n) operations with fewer rotations.

B-Tree / B+ Tree: Used in databases and file systems. Optimized for disk I/O by having many children per node.

Trie (Prefix Tree)

A trie stores strings character by character. Each node represents a prefix.

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
  }

  search(word: string): boolean {
    const node = this.traverse(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix: string): boolean {
    return this.traverse(prefix) !== null;
  }

  private traverse(s: string): TrieNode | null {
    let node = this.root;
    for (const ch of s) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch)!;
    }
    return node;
  }
}

When to use tries:

Autocomplete / prefix search
Word dictionary with prefix queries
When you need to find all strings with a given prefix efficiently

The Recursive Template

Most tree problems follow one template:

function solve(root: TreeNode | null): ResultType {
  // Base case
  if (!root) return baseValue;

  // Recurse on subtrees
  const leftResult = solve(root.left);
  const rightResult = solve(root.right);

  // Combine results with current node
  return combine(root.val, leftResult, rightResult);
}

The key insight is deciding what information flows up from children (return value) versus what flows down from parent (parameters). Master this distinction and tree problems become mechanical.

Trees

On this page