Minimal, copy-paste C++ for tree traversals, LCA (binary lifting), segment tree, Fenwick tree, and HLD skeleton.

Contents

Traversals (iterative)

vector<int> inorder(TreeNode* root){
    vector<int> ans; stack<TreeNode*> st; auto cur = root;
    while (cur || !st.empty()){
        while (cur){ st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop(); ans.push_back(cur->val); cur = cur->right;
    }
    return ans;
}

vector<vector<int>> levelOrder(TreeNode* root){
    vector<vector<int>> res; if(!root) return res; queue<TreeNode*> q; q.push(root);
    while(!q.empty()){
        int sz=q.size(); res.emplace_back();
        while(sz--){ auto* u=q.front(); q.pop(); res.back().push_back(u->val);
            if(u->left) q.push(u->left); if(u->right) q.push(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)

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

void dfs(TreeNode* node) {
    if (!node) return;
    // preorder: process here
    dfs(node->left);
    // inorder: process here
    dfs(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.

int dfs(TreeNode* node) {
    if (!node) return 0;
    int left = dfs(node->left);
    int right = dfs(node->right);
    return combine(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 = INT_MIN;

int dfs(TreeNode* node) {
    if (!node) return 0;
    int left = max(0, dfs(node->left));
    int right = max(0, dfs(node->right));
    result = max(result, left + right + node->val);
    return node->val + 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.

void dfs(TreeNode* node, vector<int>& path, vector<vector<int>>& result) {
    if (!node) return;
    path.push_back(node->val);

    if (!node->left && !node->right)
        result.push_back(path);

    dfs(node->left, path, result);
    dfs(node->right, path, result);
    path.pop_back();
}
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.

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        vector<int> level;
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(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.

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 -

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)

const int K = 17; vector<int> depth; vector<array<int,K+1>> up;
void dfsLift(int u,int p,const vector<vector<int>>& 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[u]) if(v!=p){ depth[v]=depth[u]+1; dfsLift(v,u,g);} }
int lift(int u,int k){ for(int i=0;i<=K;++i) if(k&(1<<i)) u = (u<0)?-1: up[u][i]; return u; }
int lca(int a,int b){ if(depth[a]<depth[b]) swap(a,b); 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

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)

class SegmentTree {
public:
    SegmentTree(vector<int>& nums) {
        n = nums.size();
        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(1, 0, n - 1, left, right);
    }
    
private:
    int n;
    vector<int> tree;
    
    void build(vector<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 {
public:
    SegmentTreeLazy(vector<int>& nums) {
        n = nums.size();
        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(1, 0, n - 1, left, right);
    }
    
private:
    int n;
    vector<int> tree, lazy;
    
    void build(vector<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] != 0) {
            tree[node] += 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[node] += 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 {
public:
    SegmentTree(vector<T>& arr, T identity = T(), Merge merge = Merge()) 
        : n(arr.size()), 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(1, 0, n - 1, left, right);
    }
    
private:
    int n;
    vector<T> tree;
    T identity;
    Merge merge;
    
    void build(vector<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, INT_MAX, [](int a, int b) { return min(a, b); });
// Range Max: SegmentTree<int, function<int(int,int)>> st(arr, INT_MIN, [](int a, int b) { return 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

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

Fenwick Tree (Binary Indexed Tree)

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)

class FenwickTree {
public:
    FenwickTree(int size) : n(size), BIT(size + 1, 0) {}
    
    // Add delta to element at index i (0-indexed)
    void add(int i, int delta) {
        i++; // Convert to 1-indexed
        while (i <= n) {
            BIT[i] += 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);
    }
    
private:
    int n;
    vector<int> BIT;
};

Fenwick Tree for Range Sum Query

class NumArray {
private:
    vector<int> BIT;
    vector<int> nums;
    int n;
    
    void add(int i, int delta) {
        i++;
        while (i <= n) {
            BIT[i] += delta;
            i += (i & -i);
        }
    }
    
    int prefixSum(int i) {
        int sum = 0;
        i++;
        while (i > 0) {
            sum += BIT[i];
            i -= (i & -i);
        }
        return sum;
    }
    
public:
    NumArray(vector<int>& nums) : nums(nums) {
        n = nums.size();
        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 {
public:
    FenwickTree2D(int rows, int cols) 
        : m(rows), n(cols), BIT(rows + 1, vector<int>(cols + 1, 0)) {}
    
    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);
    }
    
private:
    int m, n;
    vector<vector<int>> BIT;
};

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

HLD (Heavy-Light Decomposition) skeleton

const int N = 200000; vector<int> gH[N]; int szH[N], parH[N], depH[N], heavyH[N], headH[N], inH[N], curT=0;
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[u]+=s; if(s>best){best=s; heavyH[u]=v;} } return szH[u]; }
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