Trees

Back to DSA & Algorithms/00 - Roadmap Overview

What is a Tree?

A tree is a hierarchical data structure with a root node and children nodes. Each node has exactly one parent (except the root, which has none). No cycles.

         1           ← root (level 0)
       /   \
      2     3        ← level 1
     / \     \
    4   5     6      ← level 2 (leaves: no children)

Key Terminology

Term	Definition
Root	Top node, no parent
Leaf	Node with no children
Edge	Connection between parent and child
Depth	Distance from root to this node (root = 0)
Height	Distance from this node to deepest leaf
Level	Same as depth
Subtree	A node and all its descendants

Binary Tree

Each node has at most 2 children: left and right.

java
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

Binary Search Tree (BST)

A binary tree where: left subtree values < node < right subtree values.

This property makes search O(log n) for balanced trees.

BST:          8
            /   \
           3     10
          / \      \
         1   6     14
            / \   /
           4   7 13

Search for 6:
  8: 6 < 8 → go left
  3: 6 > 3 → go right
  6: found! (3 steps instead of scanning all 9 nodes)

Types of Binary Trees

Type	Definition
Full	Every node has 0 or 2 children
Complete	All levels full except last, filled left to right
Perfect	All leaves at same depth, all internals have 2 children
Balanced	Height difference between left/right subtree ≤ 1
Degenerate	Every node has only 1 child (basically a linked list)

The Tree Recursion Framework

Most tree problems follow this structure:

java
int solve(TreeNode node) {
    // Base case: empty tree
    if (node == null)
        return baseValue;

    // Recursive step: solve for children
    int leftResult = solve(node.left);
    int rightResult = solve(node.right);

    // Combine: use current node + children results
    return combine(node.val, leftResult, rightResult);
}

Every tree problem is asking: "Given the answers for the left and right subtrees, what's the answer for this node?"

Pattern 1: DFS Traversals

What it is

Depth-First Search: Go as deep as possible before backtracking. Three orderings based on when you process the current node.

The Three Orderings

        1
       / \
      2   3
     / \
    4   5

Inorder   (Left, Root, Right):  4, 2, 5, 1, 3   ← BST gives SORTED order
Preorder  (Root, Left, Right):  1, 2, 4, 5, 3   ← Copy/serialize tree structure
Postorder (Left, Right, Root):  4, 5, 2, 3, 1   ← Delete tree, evaluate expression

Memory Trick

INorder:   root is IN the middle    → L, Root, R
PREorder:  root is at the PREFIX    → Root, L, R
POSTorder: root is at the POSTFIX   → L, R, Root

Recursive Implementation (Simplest)

java
List<Integer> inorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    result.addAll(inorder(root.left));
    result.add(root.val);
    result.addAll(inorder(root.right));
    return result;
}

Iterative Implementation (Interviewers Sometimes Ask)

java
List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;

    while (!stack.isEmpty() || curr != null) {
        // Go as far left as possible
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }

        // Process node
        curr = stack.pop();
        result.add(curr.val);

        // Move to right subtree
        curr = curr.right;
    }

    return result;
}

// Think of it like this:
// The stack replaces the call stack of recursion.
// "Go left as far as possible" = dive deep
// "Pop" = backtrack to the most recent unprocessed node
// "Move right" = explore the right subtree

Problems

94. Binary Tree Inorder Traversal - Easy
144. Binary Tree Preorder Traversal - Easy
145. Binary Tree Postorder Traversal - Easy

Pattern 2: BFS / Level Order Traversal

What it is

Process the tree level by level, left to right. Uses a queue (not a stack!).

The Mental Model

Imagine water flooding from the root. It fills level 0 first, then level 1, then level 2... Each level is completely processed before moving to the next.

Step-by-Step

java
List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        int levelSize = queue.size();  // CRITICAL: snapshot the size before processing

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }

        result.add(level);
    }

    return result;
}

// Why snapshot levelSize?
// Because we ADD children to the queue during the loop.
// Without the snapshot, we'd process nodes from the next level too.
//
//         1
//        / \
//       2   3
//      / \
//     4   5
//
// Queue: [1], levelSize=1
//   Process 1, add 2 and 3 → Queue: [2, 3]
//   level = [1]
//
// Queue: [2, 3], levelSize=2
//   Process 2, add 4 and 5 → Queue: [3, 4, 5]
//   Process 3 → Queue: [4, 5]
//   level = [2, 3]
//
// Queue: [4, 5], levelSize=2
//   Process 4, no children. Process 5, no children.
//   level = [4, 5]
//
// Result: [[1], [2,3], [4,5]]

Right Side View

java
// See the tree from the right side → last node of each level
List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (i == levelSize - 1)      // Last node in this level
                result.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }

    return result;
}

Problems

102. Binary Tree Level Order Traversal - Medium
199. Binary Tree Right Side View - Medium
103. Binary Tree Zigzag Level Order Traversal - Medium
297. Serialize and Deserialize Binary Tree - Hard

Pattern 3: Height / Depth / Diameter

What it is

Compute properties by recursing to leaves and building up.

Maximum Depth

java
int maxDepth(TreeNode root) {
    if (root == null)
        return 0;    // Empty tree has depth 0

    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);

    return 1 + Math.max(leftDepth, rightDepth);
}

// Read this as: "My depth = 1 + the deeper of my two children"
//
//         1          depth = 1 + max(2, 1) = 3
//        / \
//       2   3        left depth = 1 + max(1, 0) = 2, right depth = 1
//      /
//     4              left depth = 1 + max(0, 0) = 1

Diameter (Longest Path Between Any Two Nodes)

java
int diameterOfBinaryTree(TreeNode root) {
    int[] maxDiameter = {0};  // Use array to allow mutation in nested method

    height(root, maxDiameter);
    return maxDiameter[0];
}

int height(TreeNode node, int[] maxDiameter) {
    if (node == null)
        return 0;

    int leftH = height(node.left, maxDiameter);
    int rightH = height(node.right, maxDiameter);

    // At each node, the longest path THROUGH this node
    // = left height + right height
    maxDiameter[0] = Math.max(maxDiameter[0], leftH + rightH);

    // Return height (for parent's calculation)
    return 1 + Math.max(leftH, rightH);
}

// Key insight: The diameter might not pass through the root!
//     1
//    /
//   2         Diameter = 4 (path: 5→3→2→4→6), doesn't go through 1
//  / \
// 3   4
// |   |
// 5   6

Balanced Binary Tree

java
boolean isBalanced(TreeNode root) {
    return check(root) != -1;
}

int check(TreeNode node) {
    if (node == null)
        return 0;

    int leftH = check(node.left);
    int rightH = check(node.right);

    // -1 means subtree is already unbalanced
    if (leftH == -1 || rightH == -1)
        return -1;
    if (Math.abs(leftH - rightH) > 1)
        return -1;

    return 1 + Math.max(leftH, rightH);
}

Problems

104. Maximum Depth of Binary Tree - Easy
543. Diameter of Binary Tree - Easy
110. Balanced Binary Tree - Easy
100. Same Tree - Easy
572. Subtree of Another Tree - Easy
226. Invert Binary Tree - Easy

Pattern 4: Path Sum / Root-to-Leaf

What it is

Track a running value (sum, path) from root to leaves.

java
boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null)
        return false;

    // Am I a leaf with the right remaining sum?
    if (root.left == null && root.right == null)
        return root.val == targetSum;

    // Subtract current value and check children
    int remaining = targetSum - root.val;
    return hasPathSum(root.left, remaining) ||
           hasPathSum(root.right, remaining);
}

// Path Sum III (any path, not just root-to-leaf)
// Use prefix sum technique (like subarray sum on a tree!)
int pathSumIII(TreeNode root, int target) {
    int[] count = {0};
    Map<Long, Integer> prefix = new HashMap<>();
    prefix.put(0L, 1);  // Empty path has sum 0

    dfs(root, 0L, target, prefix, count);
    return count[0];
}

void dfs(TreeNode node, long currSum, int target,
         Map<Long, Integer> prefix, int[] count) {
    if (node == null) return;

    currSum += node.val;
    count[0] += prefix.getOrDefault(currSum - target, 0);
    prefix.put(currSum, prefix.getOrDefault(currSum, 0) + 1);

    dfs(node.left, currSum, target, prefix, count);
    dfs(node.right, currSum, target, prefix, count);

    prefix.put(currSum, prefix.get(currSum) - 1);  // BACKTRACK: undo when leaving this path
}

Maximum Path Sum (Classic Hard)

java
int maxPathSum(TreeNode root) {
    int[] maxSum = {Integer.MIN_VALUE};
    gain(root, maxSum);
    return maxSum[0];
}

int gain(TreeNode node, int[] maxSum) {
    if (node == null)
        return 0;

    // Max gain from left/right (ignore negative contributions)
    int left = Math.max(gain(node.left, maxSum), 0);
    int right = Math.max(gain(node.right, maxSum), 0);

    // Path through this node
    maxSum[0] = Math.max(maxSum[0], node.val + left + right);

    // Return max gain if this node is part of a longer path (can only go one way)
    return node.val + Math.max(left, right);
}

// Key insight: At each node, you can USE both left and right branches
// (creating a path that peaks at this node).
// But you can only RETURN one branch to the parent
// (a path can't split — it must be a single line).

Problems

112. Path Sum - Easy
113. Path Sum II - Medium
437. Path Sum III - Medium
124. Binary Tree Maximum Path Sum - Hard

Pattern 5: BST Properties

The Key Property

Inorder traversal of a BST gives a sorted sequence. This unlocks many problems.

Validate BST

java
boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean isValidBST(TreeNode root, long lo, long hi) {
    if (root == null)
        return true;

    // Current node must be within valid range
    if (root.val <= lo || root.val >= hi)
        return false;

    // Left subtree: all values must be < root.val
    // Right subtree: all values must be > root.val
    return isValidBST(root.left, lo, root.val) &&
           isValidBST(root.right, root.val, hi);
}

// Common mistake: Only comparing with parent.
// This is WRONG: [5, 1, 6, null, null, 3, 7]
//       5
//      / \
//     1   6
//        / \
//       3   7
// 3 is less than 6 (good as left child of 6)
// But 3 is also less than 5 (BAD — it's in the right subtree of 5)
// Must pass valid RANGE, not just parent value.

Kth Smallest (Inorder is Sorted)

java
int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;

    while (!stack.isEmpty() || curr != null) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }

        curr = stack.pop();
        k--;
        if (k == 0)
            return curr.val;

        curr = curr.right;
    }

    return -1; // k is larger than tree size
}

// Inorder traversal visits nodes in sorted order.
// Stop after visiting the Kth node.

Lowest Common Ancestor in BST

java
// BST version is simpler than general BT version!
TreeNode lcaBST(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val)
            root = root.left;     // Both in left subtree
        else if (p.val > root.val && q.val > root.val)
            root = root.right;    // Both in right subtree
        else
            return root;          // Split point = LCA
    }
    return null;
}

// When p and q are on different sides (or one IS root), that's the LCA.

Problems

98. Validate Binary Search Tree - Medium
230. Kth Smallest Element in a BST - Medium
235. Lowest Common Ancestor of BST - Medium
108. Convert Sorted Array to BST - Easy

Pattern 6: Lowest Common Ancestor (General)

java
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q)
        return root;

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

    if (left != null && right != null)
        return root;          // p and q are in different subtrees → this node is LCA
    return left != null ? left : right;  // Both in same subtree → return whichever found something
}

// Why this works:
// The recursion returns the first "important" node it finds (p or q).
// If a node gets non-null from BOTH sides, it means p is on one side
// and q is on the other → this node is where they meet = LCA.

Problems

236. Lowest Common Ancestor of Binary Tree - Medium

Pattern 7: Tree Construction

From Preorder and Inorder

java
int buildTree(int[] preorder, int[] inorder) {
    // Entry point — delegates to the recursive helper
    // Returns the root of the constructed tree
}

TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++)
        inorderMap.put(inorder[i], i);

    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1, inorderMap);
}

TreeNode build(int[] preorder, int preStart, int preEnd,
               int[] inorder, int inStart, int inEnd,
               Map<Integer, Integer> inorderMap) {
    if (preStart > preEnd || inStart > inEnd)
        return null;

    // First element of preorder is always the root
    int rootVal = preorder[preStart];
    TreeNode root = new TreeNode(rootVal);

    // Find root in inorder to split left/right subtrees
    int mid = inorderMap.get(rootVal);
    int leftSize = mid - inStart;

    root.left = build(preorder, preStart + 1, preStart + leftSize,
                      inorder, inStart, mid - 1, inorderMap);
    root.right = build(preorder, preStart + leftSize + 1, preEnd,
                       inorder, mid + 1, inEnd, inorderMap);

    return root;
}

// Preorder: [3, 9, 20, 15, 7]    ← root is always first
// Inorder:  [9, 3, 15, 20, 7]    ← everything left of root is left subtree
//
// Root = 3
// Inorder split: [9] | 3 | [15, 20, 7]
// Left subtree preorder: [9], inorder: [9]
// Right subtree preorder: [20, 15, 7], inorder: [15, 20, 7]

Problems

105. Construct Binary Tree from Preorder and Inorder - Medium
106. Construct from Inorder and Postorder - Medium

Things You MUST Be Aware Of

1. Binary Tree ≠ BST

Always ask the interviewer: "Is this a BST or a general binary tree?"
BST gives you ordering guarantees → different (usually simpler) algorithms.

2. null Checks

java
// Every recursive function must handle null nodes
if (node == null)
    return ...;
// This is your base case. Forgetting it = stack overflow.

3. DFS vs BFS When?

DFS: When you need to explore paths to leaves (path sum, validate BST)
BFS: When you need level-by-level processing (level order, minimum depth)
BFS always gives shortest path in unweighted graphs/trees.

4. Global vs Return Value

java
// Some problems need a "global" answer updated during recursion
// (like diameter, max path sum)
// Use an int[] array of size 1 to mutate from helper methods
int[] maxVal = {0};
void dfs(TreeNode node) {
    maxVal[0] = Math.max(maxVal[0], ...);
}

5. Height vs Depth

Height: bottom-up (leaf = 0, root = max)
Depth:  top-down (root = 0, leaf = max)
They're related but not the same for non-root nodes.

Decision Guide

Process level by level?
  └── BFS with queue

Find path from root to leaf?
  └── DFS, pass accumulator down

Compute property of whole tree (height, count)?
  └── DFS, build result bottom-up

Is it a BST?
  └── Use BST properties (inorder = sorted, range validation)

Find LCA?
  └── BST: compare with root value
  └── General: recursive "find from both sides"

Construct tree from traversals?
  └── Preorder gives root, inorder gives left/right split