Algorithm Templates: Trees

Trees are one of the most frequently tested data structures in coding interviews. This page collects ready-to-use Java templates for every major tree pattern — from basic traversals to advanced structures like segment trees and heavy-light decomposition. Each section includes the core template, guidance on when to reach for it, and curated practice problems.

New to Trees? A tree is a connected graph with no cycles. Binary trees (each node has at most 2 children) are the most common in interviews. The key insight: most tree problems are solved with recursion — process the current node, then recurse on left and right.

Pattern Summary

| Pattern | Signal Phrases | Approach | |—|—|—| | Inorder Traversal | “sorted order of BST” | Left → Root → Right | | Bottom-Up DFS | “height”, “diameter”, “balanced” | Return value from children | | Global Result | “max path sum” | Track global max during DFS | | Path Tracking | “root-to-leaf”, “path sum” | Pass path down recursively | | Level-order BFS | “level by level”, “right side view” | Queue, process by level | | LCA | “lowest common ancestor” | Recursive or binary lifting | | BST | “validate”, “search”, “insert” | Use BST property (left < root < right) |

Contents

• Traversals (iterative)
• Tree DFS Patterns
  • Pattern 1: Basic Tree Traversal (DFS)
  • Pattern 2: DFS with Return Value (Bottom-Up)
  • Pattern 3: DFS with Global Result
  • Pattern 4: Root-to-Leaf Path Tracking
  • Pattern 5: BFS / Level Order Traversal
  • Pattern 6: Lowest Common Ancestor (LCA)
  • Pattern 7: Binary Search Tree (BST) Pattern
  • Practice Roadmap
• LCA (Binary Lifting)
• Segment Tree
• Binary Search on Segment Tree (Tree Walking)
• Fenwick Tree (Binary Indexed Tree)
• HLD (Heavy-Light Decomposition)

Traversals (iterative)

When to use: You need to visit every node in a specific order — inorder for sorted BST output, level-order for layer-by-layer processing.

ID	Title	Link	Solution
94	Binary Tree Inorder Traversal	Link	Solution
144	Binary Tree Preorder Traversal	Link	Solution
145	Binary Tree Postorder Traversal	Link	Solution
102	Binary Tree Level Order Traversal	Link	Solution
103	Binary Tree Zigzag Level Order Traversal	Link	Solution
429	N-ary Tree Level Order Traversal	Link	Solution
314	Binary Tree Vertical Order Traversal	Link	Solution

// import java.util.*;
int[]inorder(TreeNode root){
    List<Integer> ans = new ArrayList<>(); Deque<TreeNode> st = new ArrayDeque<>(); var cur = root;
    while (cur || !st.isEmpty()){
        while (cur > 0) { st.offer(cur); cur = cur.left; }
        cur = st.peek(); st.poll(); ans.add(cur.val); cur = cur.right;
    }
    return ans;
}

// import java.util.*;
int[][] levelOrder(TreeNode root){
    List<int[]> res = new ArrayList<>(); if(!root) return res; Queue<TreeNode> q = new LinkedList<>(); q.offer(root);
    while(!q.isEmpty()){
        int sz=q.size(); res.add();
        while(sz--){ var u =q.get(0); q.poll(); res.get(res.size() - 1).push_back(u.val);
            if(u.left) q.offer(u.left); if(u.right) q.offer(u.right);
        }
    }
    return res;
}

ID	Title	Link	Solution
94	Binary Tree Inorder Traversal	Link	Solution
144	Binary Tree Preorder Traversal	Link	Solution
145	Binary Tree Postorder Traversal	Link	Solution
102	Binary Tree Level Order Traversal	Link	Solution
103	Binary Tree Zigzag Level Order Traversal	Link	Solution
429	N-ary Tree Level Order Traversal	Link	Solution
314	Binary Tree Vertical Order Traversal	Link	Solution

Tree DFS Patterns

Recognizing the right tree pattern quickly is key. Below are the 7 core patterns that cover nearly all tree DFS problems.

---

Pattern 1: Basic Tree Traversal (DFS)

When to use: Simple traversal, count nodes, check a property on every node.

Traverse the tree using DFS. Most problems reduce to choosing when to process the node.

Preorder  : root → left → right
Inorder   : left → root → right
Postorder : left → right → root

ID	Title	Link	Solution
144	Binary Tree Preorder Traversal	Link	Solution
94	Binary Tree Inorder Traversal	Link	Solution
145	Binary Tree Postorder Traversal	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution

---

Pattern 2: DFS with Return Value (Bottom-Up)

When to use: Height, diameter, balanced check — any problem where the answer depends on information from both subtrees.

Each recursive call returns information about its subtree. Process children first, then combine results and return upward. Used for: height, balance, diameter, subtree properties.

ID	Title	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution
110	Balanced Binary Tree	Link	Solution
543	Diameter of Binary Tree	Link	Solution
124	Binary Tree Maximum Path Sum	Link	-
1376	Time Needed to Inform All Employees	Link	Solution

---

Pattern 3: DFS with Global Result

When to use: Max path sum, longest path — the optimal answer may span across left and right subtrees, but each recursive call can only return one branch upward.

While traversing, update a global variable tracking the best result. The recursive function returns a per-node value, but the answer lives outside the recursion.

ID	Title	Link	Solution
543	Diameter of Binary Tree	Link	Solution
124	Binary Tree Maximum Path Sum	Link	-
1448	Count Good Nodes in Binary Tree	Link	Solution

---

Pattern 4: Root-to-Leaf Path Tracking

When to use: Root-to-leaf paths, path sum collection — any problem that needs the full path from root to the current node.

Maintain a path from root to the current node. Push → recurse → pop (backtracking). Used for returning paths, validating sequences, and path sum collection.

ID	Title	Link	Solution
112	Path Sum	Link	Solution
113	Path Sum II	Link	Solution
257	Binary Tree Paths	Link	-

---

Pattern 5: BFS / Level Order Traversal

When to use: Level-order, right-side view, zigzag traversal — any problem that processes nodes layer by layer.

Traverse the tree level by level using a queue. Used for level processing, shortest depth, and breadth exploration.

ID	Title	Link	Solution
102	Binary Tree Level Order Traversal	Link	Solution
107	Binary Tree Level Order Traversal II	Link	-
111	Minimum Depth of Binary Tree	Link	Solution

---

Pattern 6: Lowest Common Ancestor (LCA)

When to use: Lowest common ancestor — find the deepest node that is an ancestor of both target nodes.

Postorder DFS: if both subtrees contain a target, the current node is the LCA.

ID	Title	Link	Solution
236	Lowest Common Ancestor of a Binary Tree	Link	Solution
235	Lowest Common Ancestor of a BST	Link	-

---

Pattern 7: Binary Search Tree (BST) Pattern

When to use: Validate BST, search, insert, delete — any problem that leverages the BST property (left < root < right) for pruning or ordered processing.

BST property: left < root < right. Inorder traversal produces sorted order. This enables pruning and ordered processing.

ID	Title	Link	Solution
98	Validate Binary Search Tree	Link	-
230	Kth Smallest Element in a BST	Link	-
235	Lowest Common Ancestor of a BST	Link	-
894	All Possible Full Binary Trees	Link	Solution

---

Practice Roadmap

Day	Focus	Problems
1	Basics	LC 104 Maximum Depth, LC 102 Level Order, LC 257 Binary Tree Paths
2	Intermediate	LC 110 Balanced Binary Tree, LC 543 Diameter, LC 236 LCA
3	Advanced	LC 98 Validate BST, LC 230 Kth Smallest in BST, LC 124 Max Path Sum

Quick Pattern Recognition

If the problem mentions height, diameter, path sum, ancestor, subtree, depth → think DFS on tree.

If the problem mentions levels, shortest depth, layer traversal → think BFS with queue.

Most tree interview problems are medium difficulty, DFS recursion, postorder reasoning. If you can confidently solve LC 543, LC 236, and LC 124, you are well-prepared for senior-level tree questions.

---

Preorder  : root → left → right
Inorder   : left → root → right
Postorder : left → right → root

ID	Title	Link	Solution
144	Binary Tree Preorder Traversal	Link	Solution
94	Binary Tree Inorder Traversal	Link	Solution
145	Binary Tree Postorder Traversal	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution

---

Pattern 2: DFS with Return Value (Bottom-Up)

When to use: Height, diameter, balanced check — any problem where the answer depends on information from both subtrees.

Each recursive call returns information about its subtree. Process children first, then combine results and return upward. Used for: height, balance, diameter, subtree properties.

ID	Title	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution
110	Balanced Binary Tree	Link	Solution
543	Diameter of Binary Tree	Link	Solution
124	Binary Tree Maximum Path Sum	Link	-
1376	Time Needed to Inform All Employees	Link	Solution

---

Pattern 3: DFS with Global Result

When to use: Max path sum, longest path — the optimal answer may span across left and right subtrees, but each recursive call can only return one branch upward.

While traversing, update a global variable tracking the best result. The recursive function returns a per-node value, but the answer lives outside the recursion.

ID	Title	Link	Solution
543	Diameter of Binary Tree	Link	Solution
124	Binary Tree Maximum Path Sum	Link	-
1448	Count Good Nodes in Binary Tree	Link	Solution

---

Pattern 4: Root-to-Leaf Path Tracking

When to use: Root-to-leaf paths, path sum collection — any problem that needs the full path from root to the current node.

Maintain a path from root to the current node. Push → recurse → pop (backtracking). Used for returning paths, validating sequences, and path sum collection.

ID	Title	Link	Solution
112	Path Sum	Link	Solution
113	Path Sum II	Link	Solution
257	Binary Tree Paths	Link	-

---

Pattern 5: BFS / Level Order Traversal

When to use: Level-order, right-side view, zigzag traversal — any problem that processes nodes layer by layer.

Traverse the tree level by level using a queue. Used for level processing, shortest depth, and breadth exploration.

ID	Title	Link	Solution
102	Binary Tree Level Order Traversal	Link	Solution
107	Binary Tree Level Order Traversal II	Link	-
111	Minimum Depth of Binary Tree	Link	Solution

---

Pattern 6: Lowest Common Ancestor (LCA)

When to use: Lowest common ancestor — find the deepest node that is an ancestor of both target nodes.

Postorder DFS: if both subtrees contain a target, the current node is the LCA.

ID	Title	Link	Solution
236	Lowest Common Ancestor of a Binary Tree	Link	Solution
235	Lowest Common Ancestor of a BST	Link	-

---

Pattern 7: Binary Search Tree (BST) Pattern

When to use: Validate BST, search, insert, delete — any problem that leverages the BST property (left < root < right) for pruning or ordered processing.

BST property: left < root < right. Inorder traversal produces sorted order. This enables pruning and ordered processing.

ID	Title	Link	Solution
98	Validate Binary Search Tree	Link	-
230	Kth Smallest Element in a BST	Link	-
235	Lowest Common Ancestor of a BST	Link	-
894	All Possible Full Binary Trees	Link	Solution

---

Practice Roadmap

Day	Focus	Problems
1	Basics	LC 104 Maximum Depth, LC 102 Level Order, LC 257 Binary Tree Paths
2	Intermediate	LC 110 Balanced Binary Tree, LC 543 Diameter, LC 236 LCA
3	Advanced	LC 98 Validate BST, LC 230 Kth Smallest in BST, LC 124 Max Path Sum

Quick Pattern Recognition

If the problem mentions height, diameter, path sum, ancestor, subtree, depth → think DFS on tree.

If the problem mentions levels, shortest depth, layer traversal → think BFS with queue.

Most tree interview problems are medium difficulty, DFS recursion, postorder reasoning. If you can confidently solve LC 543, LC 236, and LC 124, you are well-prepared for senior-level tree questions.

---

Preorder  : root → left → right
Inorder   : left → root → right
Postorder : left → right → root

ID	Title	Link	Solution
144	Binary Tree Preorder Traversal	Link	Solution
94	Binary Tree Inorder Traversal	Link	Solution
145	Binary Tree Postorder Traversal	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution

---

Pattern 2: DFS with Return Value (Bottom-Up)

When to use: Height, diameter, balanced check — any problem where the answer depends on information from both subtrees.

Each recursive call returns information about its subtree. Process children first, then combine results and return upward. Used for: height, balance, diameter, subtree properties.

ID	Title	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution
110	Balanced Binary Tree	Link	Solution
543	Diameter of Binary Tree	Link	Solution
124	Binary Tree Maximum Path Sum	Link	-
1376	Time Needed to Inform All Employees	Link	Solution

---

Pattern 3: DFS with Global Result

When to use: Max path sum, longest path — the optimal answer may span across left and right subtrees, but each recursive call can only return one branch upward.

While traversing, update a global variable tracking the best result. The recursive function returns a per-node value, but the answer lives outside the recursion.

ID	Title	Link	Solution
543	Diameter of Binary Tree	Link	Solution
124	Binary Tree Maximum Path Sum	Link	-
1448	Count Good Nodes in Binary Tree	Link	Solution

---

Pattern 4: Root-to-Leaf Path Tracking

When to use: Root-to-leaf paths, path sum collection — any problem that needs the full path from root to the current node.

Maintain a path from root to the current node. Push → recurse → pop (backtracking). Used for returning paths, validating sequences, and path sum collection.

ID	Title	Link	Solution
112	Path Sum	Link	Solution
113	Path Sum II	Link	Solution
257	Binary Tree Paths	Link	-

---

Pattern 5: BFS / Level Order Traversal

When to use: Level-order, right-side view, zigzag traversal — any problem that processes nodes layer by layer.

Traverse the tree level by level using a queue. Used for level processing, shortest depth, and breadth exploration.

ID	Title	Link	Solution
102	Binary Tree Level Order Traversal	Link	Solution
107	Binary Tree Level Order Traversal II	Link	-
111	Minimum Depth of Binary Tree	Link	Solution

---

Pattern 6: Lowest Common Ancestor (LCA)

When to use: Lowest common ancestor — find the deepest node that is an ancestor of both target nodes.

Postorder DFS: if both subtrees contain a target, the current node is the LCA.

ID	Title	Link	Solution
236	Lowest Common Ancestor of a Binary Tree	Link	Solution
235	Lowest Common Ancestor of a BST	Link	-

---

Pattern 7: Binary Search Tree (BST) Pattern

When to use: Validate BST, search, insert, delete — any problem that leverages the BST property (left < root < right) for pruning or ordered processing.

BST property: left < root < right. Inorder traversal produces sorted order. This enables pruning and ordered processing.

ID	Title	Link	Solution
98	Validate Binary Search Tree	Link	-
230	Kth Smallest Element in a BST	Link	-
235	Lowest Common Ancestor of a BST	Link	-
894	All Possible Full Binary Trees	Link	Solution

---

Practice Roadmap

Day	Focus	Problems
1	Basics	LC 104 Maximum Depth, LC 102 Level Order, LC 257 Binary Tree Paths
2	Intermediate	LC 110 Balanced Binary Tree, LC 543 Diameter, LC 236 LCA
3	Advanced	LC 98 Validate BST, LC 230 Kth Smallest in BST, LC 124 Max Path Sum

Quick Pattern Recognition

If the problem mentions height, diameter, path sum, ancestor, subtree, depth → think DFS on tree.

If the problem mentions levels, shortest depth, layer traversal → think BFS with queue.

Most tree interview problems are medium difficulty, DFS recursion, postorder reasoning. If you can confidently solve LC 543, LC 236, and LC 124, you are well-prepared for senior-level tree questions.

---

Preorder  : root → left → right
Inorder   : left → root → right
Postorder : left → right → root

ID	Title	Link	Solution
144	Binary Tree Preorder Traversal	Link	Solution
94	Binary Tree Inorder Traversal	Link	Solution
145	Binary Tree Postorder Traversal	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution

---

Pattern 2: DFS with Return Value (Bottom-Up)

When to use: Height, diameter, balanced check — any problem where the answer depends on information from both subtrees.

Each recursive call returns information about its subtree. Process children first, then combine results and return upward. Used for: height, balance, diameter, subtree properties.

ID	Title	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution
110	Balanced Binary Tree	Link	Solution
543	Diameter of Binary Tree	Link	Solution
124	Binary Tree Maximum Path Sum	Link	-
1376	Time Needed to Inform All Employees	Link	Solution

---

Pattern 3: DFS with Global Result

When to use: Max path sum, longest path — the optimal answer may span across left and right subtrees, but each recursive call can only return one branch upward.

While traversing, update a global variable tracking the best result. The recursive function returns a per-node value, but the answer lives outside the recursion.

ID	Title	Link	Solution
543	Diameter of Binary Tree	Link	Solution
124	Binary Tree Maximum Path Sum	Link	-
1448	Count Good Nodes in Binary Tree	Link	Solution

---

Pattern 4: Root-to-Leaf Path Tracking

When to use: Root-to-leaf paths, path sum collection — any problem that needs the full path from root to the current node.

Maintain a path from root to the current node. Push → recurse → pop (backtracking). Used for returning paths, validating sequences, and path sum collection.

ID	Title	Link	Solution
112	Path Sum	Link	Solution
113	Path Sum II	Link	Solution
257	Binary Tree Paths	Link	-

---

Pattern 5: BFS / Level Order Traversal

When to use: Level-order, right-side view, zigzag traversal — any problem that processes nodes layer by layer.

Traverse the tree level by level using a queue. Used for level processing, shortest depth, and breadth exploration.

ID	Title	Link	Solution
102	Binary Tree Level Order Traversal	Link	Solution
107	Binary Tree Level Order Traversal II	Link	-
111	Minimum Depth of Binary Tree	Link	Solution

---

Pattern 6: Lowest Common Ancestor (LCA)

When to use: Lowest common ancestor — find the deepest node that is an ancestor of both target nodes.

Postorder DFS: if both subtrees contain a target, the current node is the LCA.

ID	Title	Link	Solution
236	Lowest Common Ancestor of a Binary Tree	Link	Solution
235	Lowest Common Ancestor of a BST	Link	-

---

Pattern 7: Binary Search Tree (BST) Pattern

When to use: Validate BST, search, insert, delete — any problem that leverages the BST property (left < root < right) for pruning or ordered processing.

BST property: left < root < right. Inorder traversal produces sorted order. This enables pruning and ordered processing.

ID	Title	Link	Solution
98	Validate Binary Search Tree	Link	-
230	Kth Smallest Element in a BST	Link	-
235	Lowest Common Ancestor of a BST	Link	-
894	All Possible Full Binary Trees	Link	Solution

---

Practice Roadmap

Day	Focus	Problems
1	Basics	LC 104 Maximum Depth, LC 102 Level Order, LC 257 Binary Tree Paths
2	Intermediate	LC 110 Balanced Binary Tree, LC 543 Diameter, LC 236 LCA
3	Advanced	LC 98 Validate BST, LC 230 Kth Smallest in BST, LC 124 Max Path Sum

Quick Pattern Recognition

If the problem mentions height, diameter, path sum, ancestor, subtree, depth → think DFS on tree.

If the problem mentions levels, shortest depth, layer traversal → think BFS with queue.

Most tree interview problems are medium difficulty, DFS recursion, postorder reasoning. If you can confidently solve LC 543, LC 236, and LC 124, you are well-prepared for senior-level tree questions.

---

Preorder  : root → left → right
Inorder   : left → root → right
Postorder : left → right → root

static void dfs(TreeNode node) {
    if (!node) return;
    // preorder: process here dfs = new here(node.left);
    // inorder: process here dfs = new here(node.right);
    // postorder: process here
}

ID	Title	Link	Solution
144	Binary Tree Preorder Traversal	Link	Solution
94	Binary Tree Inorder Traversal	Link	Solution
145	Binary Tree Postorder Traversal	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution

---

Pattern 2: DFS with Return Value (Bottom-Up)

Each recursive call returns information about its subtree. Process children first, then combine results and return upward. Used for: height, balance, diameter, subtree properties.

static int dfs(TreeNode node) {
    if (!node) return 0;
    int left = dfs(node.left);
    int right = dfs(node.right);
    return combine = new return(left, right, node);
}

ID	Title	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution
110	Balanced Binary Tree	Link	Solution
543	Diameter of Binary Tree	Link	Solution
124	Binary Tree Maximum Path Sum	Link	-
1376	Time Needed to Inform All Employees	Link	Solution

---

Pattern 3: DFS with Global Result

While traversing, update a global variable tracking the best result. The recursive function returns a per-node value, but the answer lives outside the recursion.

int result = Integer.MIN_VALUE;

static int dfs(TreeNode node) {
    if (!node) return 0;
    int left = Math.max(0, dfs(node.left));
    int right = Math.max(0, dfs(node.right));
    result = Math.max(result, left + right + node.val);
    return node.val + Math.max(left, right);
}

ID	Title	Link	Solution
543	Diameter of Binary Tree	Link	Solution
124	Binary Tree Maximum Path Sum	Link	-
1448	Count Good Nodes in Binary Tree	Link	Solution

---

Pattern 4: Root-to-Leaf Path Tracking

Maintain a path from root to the current node. Push → recurse → pop (backtracking). Used for returning paths, validating sequences, and path sum collection.

static void dfs(TreeNode node, int[] path, int[][] result) {
    if (!node) return;
    path.add(node.val);

    if (!node.left && !node.right)
        result.add(path);

    dfs(node.left, path, result);
    dfs(node.right, path, result);
    path.removeLast();
}

ID	Title	Link	Solution
112	Path Sum	Link	Solution
113	Path Sum II	Link	Solution
257	Binary Tree Paths	Link	-

---

Pattern 5: BFS / Level Order Traversal

Traverse the tree level by level using a queue. Used for level processing, shortest depth, and breadth exploration.

// import java.util.*;
int[][] levelOrder(TreeNode root) {
    List<int[]> result = new ArrayList<>();
    if (!root) return result;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.get(0); q.poll();
            level.add(node.val);
            if (node.left) q.offer(node.left);
            if (node.right) q.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

ID	Title	Link	Solution
102	Binary Tree Level Order Traversal	Link	Solution
107	Binary Tree Level Order Traversal II	Link	-
111	Minimum Depth of Binary Tree	Link	Solution

---

Pattern 6: Lowest Common Ancestor (LCA)

Postorder DFS: if both subtrees contain a target, the current node is the LCA.

TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (!root || root == p || root == q) return root;
    TreeNode left = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

ID	Title	Link	Solution
236	Lowest Common Ancestor of a Binary Tree	Link	Solution
235	Lowest Common Ancestor of a BST	Link	-

---

Pattern 7: Binary Search Tree (BST) Pattern

BST property: left < root < right. Inorder traversal produces sorted order. This enables pruning and ordered processing.

static void inorder(TreeNode node) {
    if (!node) return;
    inorder(node.left);
    process(node);
    inorder(node.right);
}

ID	Title	Link	Solution
98	Validate Binary Search Tree	Link	-
230	Kth Smallest Element in a BST	Link	-
235	Lowest Common Ancestor of a BST	Link	-
894	All Possible Full Binary Trees	Link	Solution

---

Practice Roadmap

Day	Focus	Problems
1	Basics	LC 104 Maximum Depth, LC 102 Level Order, LC 257 Binary Tree Paths
2	Intermediate	LC 110 Balanced Binary Tree, LC 543 Diameter, LC 236 LCA
3	Advanced	LC 98 Validate BST, LC 230 Kth Smallest in BST, LC 124 Max Path Sum

Quick Pattern Recognition

If the problem mentions height, diameter, path sum, ancestor, subtree, depth → think DFS on tree.

If the problem mentions levels, shortest depth, layer traversal → think BFS with queue.

Most tree interview problems are medium difficulty, DFS recursion, postorder reasoning. If you can confidently solve LC 543, LC 236, and LC 124, you are well-prepared for senior-level tree questions.

---

LCA (Binary Lifting)

When to use: Multiple LCA queries on a static tree, or when you also need to find the k-th ancestor of a node. Preprocess in O(N log N), answer each query in O(log N).

ID	Title	Link	Solution
236	Lowest Common Ancestor of a Binary Tree	Link	Solution
235	Lowest Common Ancestor of a BST	Link	-
1650	Lowest Common Ancestor of a Binary Tree III	Link	Solution
270	Closest Binary Search Tree Value	Link	Solution
285	Inorder Successor in BST	Link	Solution
426	Convert Binary Search Tree to Sorted Doubly Linked List	Link	Solution
938	Range Sum of BST	Link	Solution
100	Same Tree	Link	Solution
101	Symmetric Tree	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution
110	Balanced Binary Tree	Link	Solution
111	Minimum Depth of Binary Tree	Link	Solution
112	Path Sum	Link	Solution
113	Path Sum II	Link	Solution
226	Invert Binary Tree	Link	Solution
543	Diameter of Binary Tree	Link	Solution
437	Path Sum III	Link	Solution
129	Sum Root to Leaf Numbers	Link	Solution
863	All Nodes Distance K in Binary Tree	Link	Solution
545	Boundary of Binary Tree	Link	Solution
993	Cousins in Binary Tree	Link	Solution
1443	Minimum Time to Collect All Apples in a Tree	Link	Solution

int K = 17;
int[] depth;
int[][] up;

static void dfsLift(int u, int p, List<List<Integer>> g) {
    up[u][0] = p;
    for (int k = 1; k <= K; k++) {
        up[u][k] = up[u][k - 1] < 0 ? -1 : up[up[u][k - 1]][k - 1];
    }
    for (int v : g.get(u)) {
        if (v != p) {
            depth[v] = depth[u] + 1;
            dfsLift(v, u, g);
        }
    }
}

static int lift(int u, int steps) {
    for (int i = 0; i <= K; i++) {
        if ((steps & (1 << i)) != 0) {
            u = u < 0 ? -1 : up[u][i];
        }
    }
    return u;
}

static int lca(int a, int b) {
    if (depth[a] < depth[b]) {
        int tmp = a; a = b; b = tmp;
    }
    a = lift(a, depth[a] - depth[b]);
    if (a == b) return a;
    for (int i = K; i >= 0; i--) {
        if (up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

ID	Title	Link	Solution
236	Lowest Common Ancestor of a Binary Tree	Link	Solution
235	Lowest Common Ancestor of a BST	Link	-
1650	Lowest Common Ancestor of a Binary Tree III	Link	Solution
270	Closest Binary Search Tree Value	Link	Solution
285	Inorder Successor in BST	Link	Solution
426	Convert Binary Search Tree to Sorted Doubly Linked List	Link	Solution
938	Range Sum of BST	Link	Solution
100	Same Tree	Link	Solution
101	Symmetric Tree	Link	Solution
104	Maximum Depth of Binary Tree	Link	Solution
110	Balanced Binary Tree	Link	Solution
111	Minimum Depth of Binary Tree	Link	Solution
112	Path Sum	Link	Solution
113	Path Sum II	Link	Solution
226	Invert Binary Tree	Link	Solution
543	Diameter of Binary Tree	Link	Solution
437	Path Sum III	Link	Solution
129	Sum Root to Leaf Numbers	Link	Solution
863	All Nodes Distance K in Binary Tree	Link	Solution
545	Boundary of Binary Tree	Link	Solution
993	Cousins in Binary Tree	Link	Solution
1443	Minimum Time to Collect All Apples in a Tree	Link	Solution

Segment Tree

When to use: Range queries (sum, min, max) with interleaved point or range updates — whenever a prefix-sum array would be too slow because of frequent modifications.

Segment Tree is a data structure that allows efficient range queries and range updates on an array. It’s particularly useful for problems involving range sum, range minimum/maximum, and range updates.

Reference: A Recursive Approach to Segment Trees, Range Sum Queries, and Lazy Propagation

Basic Segment Tree (Range Sum Query)

Segment Tree with Lazy Propagation (Range Update)

Generic Segment Tree Template

Binary Search on Segment Tree (Tree Walking)

Instead of doing a binary search over an index and then a segment tree query (O(log^2 N)), we descend the segment tree directly to find the first element satisfying a condition in O(log N).

Template: Find First Index >= X

Key Concepts

1. Tree Structure: Binary tree where each node represents a range [l, r]
2. Build: O(n) - Construct tree from array
3. Point Update: O(log n) - Update single element
4. Range Query: O(log n) - Query sum/min/max over range
5. Lazy Propagation: O(log n) - Defer range updates for efficiency
6. Space Complexity: O(4n) - Array-based representation

When to Use

• Range Queries: Sum, min, max, gcd over ranges
• Range Updates: Add/subtract value to all elements in range
• Frequent Updates: When updates and queries are interleaved
• Large Arrays: When brute force is too slow

Easy

ID	Title	Link	Solution
303	Range Sum Query - Immutable	Link	-
307	Range Sum Query - Mutable	Link	Solution

Medium

ID	Title	Link	Solution
307	Range Sum Query - Mutable	Link	Solution
308	Range Sum Query 2D - Mutable	Link	-
715	Range Module	Link	-
729	My Calendar I	Link	Solution
731	My Calendar II	Link	-
1177	Can Make Palindrome from Substring	Link	-
1505	Minimum Possible Integer After at Most K Swaps	Link	-
1649	Create Sorted Array through Instructions	Link	-
3477	Number of Unplaced Fruits	Link	Solution

Hard

ID	Title	Link	Solution
218	The Skyline Problem	Link	Solution
699	Falling Squares	Link	-
715	Range Module	Link	-
732	My Calendar III	Link	Solution
850	Rectangle Area II	Link	Solution
1157	Online Majority Element In Subarray	Link	-
2407	Longest Increasing Subsequence II	Link	-

References

• LeetCode: A Recursive Approach to Segment Trees, Range Sum Queries, and Lazy Propagation - Comprehensive guide to segment trees with examples

class SegmentTree {
    SegmentTree(int[] nums) {
        n = nums.length;
        tree.resize(4 n);
        build(nums, 1, 0, n - 1);
    }

    void update(int index, int val) {
        update(1, 0, n - 1, index, val);
    }

    int query(int left, int right) {
        return query = new return(1, 0, n - 1, left, right);
    }
    int n;
    List<Integer> tree = new ArrayList<>();

    void build(int[] nums, int node, int l, int r) {
        if (l == r) {
            tree[node] = nums[l];
        } else {
            int mid = (l + r) / 2;
            build(nums, node 2, l, mid);
            build(nums, node 2 + 1, mid + 1, r);
            tree[node] = tree[node 2] + tree[node 2 + 1];
        }
    }

    void update(int node, int l, int r, int idx, int val) {
        if (l == r) {
            tree[node] = val;
        } else {
            int mid = (l + r) / 2;
            if (idx <= mid) {
                update(node 2, l, mid, idx, val);
            } else {
                update(node 2 + 1, mid + 1, r, idx, val);
            }
            tree[node] = tree[node 2] + tree[node 2 + 1];
        }
    }

    int query(int node, int l, int r, int ql, int qr) {
        if (qr < l || ql > r) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return query(node 2, l, mid, ql, qr) +
               query(node 2 + 1, mid + 1, r, ql, qr);
    }
}

Segment Tree with Lazy Propagation (Range Update)

class SegmentTreeLazy {
    SegmentTreeLazy(int[] nums) {
        n = nums.length;
        tree.resize(4 n);
        lazy.resize(4 n, 0);
        build(nums, 1, 0, n - 1);
    }

    void updateRange(int left, int right, int val) {
        updateRange(1, 0, n - 1, left, right, val);
    }

    int query(int left, int right) {
        return query = new return(1, 0, n - 1, left, right);
    }
    int n;
    int[]tree, lazy;

    void build(int[] nums, int node, int l, int r) {
        if (l == r) {
            tree[node] = nums[l];
        } else {
            int mid = (l + r) / 2;
            build(nums, node 2, l, mid);
            build(nums, node 2 + 1, mid + 1, r);
            tree[node] = tree[node 2] + tree[node 2 + 1];
        }
    }

    void push(int node, int l, int r) {
        if (lazy[node] !) {
            tree.put(node, tree.getOrDefault(node, 0) + lazy[node] * (r - l + 1);
            if (l != r) {
                lazy[node 2] += lazy[node];
                lazy[node 2 + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    void updateRange(int node, int l, int r, int ql, int qr, int val) {
        push(node, l, r);
        if (qr < l || ql > r) return;
        if (ql <= l && r <= qr) {
            lazy.put(node, lazy.getOrDefault(node, 0) + val;
            push(node, l, r);
            return;
        }
        int mid = (l + r) / 2;
        updateRange(node 2, l, mid, ql, qr, val);
        updateRange(node 2 + 1, mid + 1, r, ql, qr, val);
        push(node 2, l, mid);
        push(node 2 + 1, mid + 1, r);
        tree[node] = tree[node 2] + tree[node 2 + 1];
    }

    int query(int node, int l, int r, int ql, int qr) {
        push(node, l, r);
        if (qr < l || ql > r) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return query(node 2, l, mid, ql, qr) +
               query(node 2 + 1, mid + 1, r, ql, qr);
    }
}

Generic Segment Tree Template

template<typename T, typename Merge = plus<T>>
class SegmentTree {
    SegmentTree(T[] arr, T identity = T(), Merge merge = Merge())
        : n(arr.length), tree(4 n), identity(identity), merge(merge) {
        build(arr, 1, 0, n - 1);
    }

    void update(int index, T val) {
        update(1, 0, n - 1, index, val);
    }

    T query(int left, int right) {
        return query = new return(1, 0, n - 1, left, right);
    }
    int n;
    T[]tree;
    T identity;
    Merge merge;

    void build(T[] arr, int node, int l, int r) {
        if (l == r) {
            tree[node] = arr[l];
        } else {
            int mid = (l + r) / 2;
            build(arr, node 2, l, mid);
            build(arr, node 2 + 1, mid + 1, r);
            tree[node] = merge(tree[node 2], tree[node 2 + 1]);
        }
    }

    void update(int node, int l, int r, int idx, T val) {
        if (l == r) {
            tree[node] = val;
        } else {
            int mid = (l + r) / 2;
            if (idx <= mid) {
                update(node 2, l, mid, idx, val);
            } else {
                update(node 2 + 1, mid + 1, r, idx, val);
            }
            tree[node] = merge(tree[node 2], tree[node 2 + 1]);
        }
    }

    T query(int node, int l, int r, int ql, int qr) {
        if (qr < l || ql > r) return identity;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return merge(query(node 2, l, mid, ql, qr),
                     query(node 2 + 1, mid + 1, r, ql, qr));
    }
}
// Usage examples:
// Range Sum: SegmentTree<int> st(arr, 0);
// Range Min: SegmentTree<int, function<int(int,int)>> st(arr, Integer.MAX_VALUE, [](int a, int b) { return Math.min(a, b); });
// Range Max: SegmentTree<int, function<int(int,int)>> st(arr, Integer.MIN_VALUE, [](int a, int b) { return Math.max(a, b); });

Binary Search on Segment Tree (Tree Walking)

Instead of doing a binary search over an index and then a segment tree query ($O(\log^2 N)$), we descend the segment tree directly to find the first element satisfying a condition in $O(\log N)$.

Template: Find First Index >= X

static int findFirst(Node node, int l, int r, int x) {
    if (node.maxVal < x) return -1;
    if (l == r) return l;

    int mid = l + (r - l) / 2;
    int res = findFirst(node.left, l, mid, x);
    if (res == -1) {
        res = findFirst(node.right, mid + 1, r, x);
    }
    return res;
}

Key Concepts

1. Tree Structure: Binary tree where each node represents a range [l, r]
2. Build: O(n) - Construct tree from array
3. Point Update: O(log n) - Update single element
4. Range Query: O(log n) - Query sum/min/max over range
5. Lazy Propagation: O(log n) - Defer range updates for efficiency
6. Space Complexity: O(4n) - Array-based representation

When to Use

• Range Queries: Sum, min, max, gcd over ranges
• Range Updates: Add/subtract value to all elements in range
• Frequent Updates: When updates and queries are interleaved
• Large Arrays: When brute force is too slow

Easy

ID	Title	Link	Solution
303	Range Sum Query - Immutable	Link	-
307	Range Sum Query - Mutable	Link	Solution

Medium

ID	Title	Link	Solution
307	Range Sum Query - Mutable	Link	Solution
308	Range Sum Query 2D - Mutable	Link	-
715	Range Module	Link	-
729	My Calendar I	Link	Solution
731	My Calendar II	Link	-
1177	Can Make Palindrome from Substring	Link	-
1505	Minimum Possible Integer After at Most K Swaps	Link	-
1649	Create Sorted Array through Instructions	Link	-
3477	Number of Unplaced Fruits	Link	Solution

Hard

ID	Title	Link	Solution
218	The Skyline Problem	Link	Solution
699	Falling Squares	Link	-
715	Range Module	Link	-
732	My Calendar III	Link	Solution
850	Rectangle Area II	Link	Solution
1157	Online Majority Element In Subarray	Link	-
2407	Longest Increasing Subsequence II	Link	-

References

• LeetCode: A Recursive Approach to Segment Trees, Range Sum Queries, and Lazy Propagation - Comprehensive guide to segment trees with examples

Fenwick Tree (Binary Indexed Tree)

When to use: Prefix sums with point updates, especially when you want simpler code and lower memory than a segment tree. Not suitable for min/max queries or range updates.

Fenwick Tree (also known as Binary Indexed Tree or BIT) is a data structure that provides efficient methods for calculating prefix sums and updating array elements. It’s more space-efficient than Segment Tree but less flexible.

Basic Fenwick Tree (1-Indexed)

Fenwick Tree for Range Sum Query

2D Fenwick Tree

Key Concepts

1. 1-Indexed Array: BIT uses 1-indexed array internally (index 0 is unused)
2. Lowest Set Bit: i & -i extracts the lowest set bit
3. Update: Add delta to node and all ancestors: i += (i & -i)
4. Query: Sum from node to root: i -= (i & -i)
5. Space Complexity: O(n) - More efficient than Segment Tree’s O(4n)
6. Time Complexity: O(log n) for both update and query

How It Works

• Tree Structure: Each node stores sum of a range ending at that index
• Update Path: When updating index i, update all nodes that include i
• Query Path: When querying prefix sum up to i, sum all nodes on path to root
• Range Query: rangeSum(l, r) = prefixSum(r) - prefixSum(l-1)

When to Use

• Prefix Sum Queries: Efficient prefix sum calculations
• Point Updates: Single element updates
• Space Constraint: When O(n) space is preferred over O(4n)
• Range Sum: When only range sum is needed (not min/max)
• Not Suitable For: Range updates, min/max queries, complex range operations

Comparison: Segment Tree vs Fenwick Tree

Aspect	Segment Tree	Fenwick Tree
Space	O(4n)	O(n)
Build Time	O(n)	O(n log n)
Update	O(log n)	O(log n)
Range Query	O(log n)	O(log n)
Range Update	O(log n) with lazy	Not directly supported
Min/Max Query	Supported	Not directly supported
Code Complexity	More verbose	Simpler
Flexibility	High	Limited to prefix/range sum

Example Problems

ID	Title	Link	Solution
307	Range Sum Query - Mutable	Link	Solution
308	Range Sum Query 2D - Mutable	Link	-
315	Count of Smaller Numbers After Self	Link	Solution
327	Count of Range Sum	Link	-
493	Reverse Pairs	Link	-
1649	Create Sorted Array through Instructions	Link	-

References

• TopCoder: Binary Indexed Trees - Comprehensive tutorial on Fenwick Trees
• GeeksforGeeks: Binary Indexed Tree - Implementation and examples

class FenwickTree {
    FenwickTree(int size) {}

    // Add delta to element at index i (0-indexed)
    void add(int i, int delta) {
        i++; // Convert to 1-indexed
        while (i <= n) {
            BIT.put(i, BIT.getOrDefault(i, 0) + delta;
            i += (i & -i); // Move to next node
        }
    }

    // Get prefix sum from [0, i] (0-indexed)
    int prefixSum(int i) {
        int sum = 0;
        i++; // Convert to 1-indexed
        while (i > 0) {
            sum += BIT[i];
            i -= (i & -i); // Move to parent
        }
        return sum;
    }

    // Get range sum from [l, r] (0-indexed)
    int rangeSum(int l, int r) {
        return prefixSum(r) - (l > 0 ? prefixSum(l - 1) : 0);
    }
    int n;
    List<Integer> BIT = new ArrayList<>();
}

Fenwick Tree for Range Sum Query

class NumArray {
    List<Integer> BIT = new ArrayList<>();
    List<Integer> nums = new ArrayList<>();
        int n;

    void add(int i, int delta) {
        i++;
        while (i <= n) {
            BIT.put(i, BIT.getOrDefault(i, 0) + delta;
            i += (i & -i);
        }
    }

    int prefixSum(int i) {
        int sum = 0;
        i++;
        while (i > 0) {
            sum += BIT[i];
            i -= (i & -i);
        }
        return sum;
    }
    NumArray(int[] nums) {
        n = nums.length;
        BIT.assign(n + 1, 0);
        for (int i = 0; i < n; i++) {
            add(i, nums[i]);
        }
    }

    void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        add(index, delta);
    }

    int sumRange(int left, int right) {
        return prefixSum(right) - (left > 0 ? prefixSum(left - 1) : 0);
    }
}

2D Fenwick Tree

class FenwickTree2D {
    FenwickTree2D(int rows, int cols) {}

    void add(int row, int col, int delta) {
        row++; col++;
        for (int i = row; i <= m; i += (i & -i)) {
            for (int j = col; j <= n; j += (j & -j)) {
                BIT[i][j] += delta;
            }
        }
    }

    int prefixSum(int row, int col) {
        int sum = 0;
        row++; col++;
        for (int i = row; i > 0; i -= (i & -i)) {
            for (int j = col; j > 0; j -= (j & -j)) {
                sum += BIT[i][j];
            }
        }
        return sum;
    }

    int rangeSum(int r1, int c1, int r2, int c2) {
        return prefixSum(r2, c2)
             - prefixSum(r1 - 1, c2)
             - prefixSum(r2, c1 - 1)
             + prefixSum(r1 - 1, c1 - 1);
    }
    int m, n;
    List<int[]> BIT = new ArrayList<>();
}

Key Concepts

1. 1-Indexed Array: BIT uses 1-indexed array internally (index 0 is unused)
2. Lowest Set Bit: i & -i extracts the lowest set bit
3. Update: Add delta to node and all ancestors: i += (i & -i)
4. Query: Sum from node to root: i -= (i & -i)
5. Space Complexity: O(n) - More efficient than Segment Tree’s O(4n)
6. Time Complexity: O(log n) for both update and query

How It Works

• Tree Structure: Each node stores sum of a range ending at that index
• Update Path: When updating index i, update all nodes that include i
• Query Path: When querying prefix sum up to i, sum all nodes on path to root
• Range Query: rangeSum(l, r) = prefixSum(r) - prefixSum(l-1)

When to Use

• Prefix Sum Queries: Efficient prefix sum calculations
• Point Updates: Single element updates
• Space Constraint: When O(n) space is preferred over O(4n)
• Range Sum: When only range sum is needed (not min/max)
• Not Suitable For: Range updates, min/max queries, complex range operations

Comparison: Segment Tree vs Fenwick Tree

Aspect	Segment Tree	Fenwick Tree
Space	O(4n)	O(n)
Build Time	O(n)	O(n log n)
Update	O(log n)	O(log n)
Range Query	O(log n)	O(log n)
Range Update	O(log n) with lazy	Not directly supported
Min/Max Query	Supported	Not directly supported
Code Complexity	More verbose	Simpler
Flexibility	High	Limited to prefix/range sum

Example Problems

ID	Title	Link	Solution
307	Range Sum Query - Mutable	Link	Solution
308	Range Sum Query 2D - Mutable	Link	-
315	Count of Smaller Numbers After Self	Link	Solution
327	Count of Range Sum	Link	-
493	Reverse Pairs	Link	-
1649	Create Sorted Array through Instructions	Link	-

References

• TopCoder: Binary Indexed Trees - Comprehensive tutorial on Fenwick Trees
• GeeksforGeeks: Binary Indexed Tree - Implementation and examples

HLD (Heavy-Light Decomposition) skeleton

When to use: Path queries or path updates on a tree (e.g., sum/max along a path between two nodes). Decomposes the tree into chains so you can use a segment tree on each chain. Rarely needed on LeetCode, but essential for competitive programming.

Note: HLD is rarely required on LeetCode.

int N = 200000; int[]gH[N]; int szH[N], parH[N], depH[N], heavyH[N], headH[N], inH[N], curT=0;
static int dfs1(int u,int p){ parH[u]=p; depH[u]=(p==-1?0:depH[p]+1); szH[u]=1; heavyH[u]=-1; int best=0; for(int v:gH[u]) if(v!=p){ int s=dfs1(v,u); szH.put(u, szH.getOrDefault(u, 0) + s; if(s>best){best=s; heavyH[u]=v;} } return szH[u]; }
static void dfs2(int u,int h){ headH[u]=h; inH[u]=curT++; if(heavyH[u]!=-1){ dfs2(heavyH[u],h); for(int v:gH[u]) if(v!=parH[u] && v!=heavyH[u]) dfs2(v,v);} }

Note: HLD is rarely required on LeetCode.

More templates

• Beginner’s Guide: LeetCode Beginner’s Guide
• Data structures (segment tree, Fenwick, DSU): Data Structures & Core Algorithms
• Graph (BFS, Dijkstra, topo): Graph
• Search (binary search, 2D): Search
• Master index: Categories & Templates