Trees are one of the most frequently tested data structures in coding interviews. This page collects ready-to-use C++ 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.

1 2 3 4 5 root left child right child leaf leaf Preorder: 1 → 2 → 4 → 3 → 5 (root, left, right) Inorder: 4 → 2 → 1 → 3 → 5 (left, root, right) Postorder: 4 → 2 → 5 → 3 → 1 (left, right, root)

Contents

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.

from collections import deque
from typing import Optional


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


def inorder(root: Optional[TreeNode]) -> list[int]:
    ans = []
    st = []
    cur = root
    while cur or st:
        while cur:
            st.append(cur)
            cur = cur.left
        cur = st.pop()
        ans.append(cur.val)
        cur = cur.right
    return ans


def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    if not root:
        return []
    res = []
    q = deque([root])
    while q:
        sz = len(q)
        level = []
        for _ in range(sz):
            u = q.popleft()
            level.append(u.val)
            if u.left:
                q.append(u.left)
            if u.right:
                q.append(u.right)
        res.append(level)
    return res

def build_lca(g: list[list[int]], root: int = 0):
    n = len(g)
    LOG = (n - 1).bit_length()
    up = [[-1] * LOG for _ in range(n)]
    depth = [0] * n

    def dfs(u: int, p: int) -> None:
        up[u][0] = p
        for k in range(1, LOG):
            prev = up[u][k - 1]
            up[u][k] = -1 if prev == -1 else up[prev][k - 1]
        for v in g[u]:
            if v == p:
                continue
            depth[v] = depth[u] + 1
            dfs(v, u)

    dfs(root, -1)

    def lift(u: int, d: int) -> int:
        for k in range(LOG):
            if (d >> k) & 1:
                u = up[u][k]
                if u == -1:
                    break
        return u

    def lca(a: int, b: int) -> int:
        if depth[a] < depth[b]:
            a, b = b, a
        a = lift(a, depth[a] - depth[b])
        if a == b:
            return a
        for k in range(LOG - 1, -1, -1):
            if up[a][k] != up[b][k]:
                a = up[a][k]
                b = up[b][k]
        return up[a][0]

    return lca, depth, up
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

def hld_build(g: list[list[int]], root: int = 0):
    n = len(g)
    parent = [-1] * n
    depth = [0] * n
    size = [0] * n
    heavy = [-1] * n
    head = [0] * n
    pos = [0] * n
    cur = 0

    def dfs1(u: int, p: int) -> int:
        parent[u] = p
        size[u] = 1
        best = 0
        for v in g[u]:
            if v == p:
                continue
            depth[v] = depth[u] + 1
            s = dfs1(v, u)
            size[u] += s
            if s > best:
                best = s
                heavy[u] = v
        return size[u]

    def dfs2(u: int, h: int) -> None:
        nonlocal cur
        head[u] = h
        pos[u] = cur
        cur += 1
        if heavy[u] != -1:
            dfs2(heavy[u], h)
        for v in g[u]:
            if v != parent[u] and v != heavy[u]:
                dfs2(v, v)

    dfs1(root, -1)
    dfs2(root, root)
    return parent, depth, size, heavy, head, pos
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.

Computing Max Depth — values return upward ↑ 0 ↑ 0 ↑ 1 ↑ 0 1 2 3 4 5 1 + max(1, 0) = 2 1+max(0,0) = 1 leaf → 0 leaf → 0 leaf → 0 Result: depth = 2 ↑ n return value 
def dfs(node):
    if not node:
        return 0
    left = dfs(node.left)
    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

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.

result = float("-inf")


def dfs(node):
    global result
    if not node:
        return 0
    left = max(0, dfs(node.left))
    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

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.

Path Tracking — collecting root-to-leaf path [1→2→4] 1 2 3 4 ✓ leaf 5 push → recurse → pop push(1) path = [1] push(2) path = [1, 2] push(4) path = [1, 2, 4] ✓ leaf → result.add([1, 2, 4]) pop(4) → path = [1, 2] pop(2) → path = [1] backtracking restores path state 
def dfs(node, path, result):
    if not node:
        return
    path.append(node.val)

    if not node.left and not node.right:
        result.append(path[:])

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

from collections import deque


def levelOrder(root):
    result = []
    if not root:
        return result
    q = deque([root])

    while q:
        size = len(q)
        level = []
        for _ in range(size):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(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)

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.

Lowest Common Ancestor — p=5, q=1 3 ★ LCA 5 p 1 q 6 2 0 8 left = found p ✓ right = found q ✓ left && right → return root (node 3 is LCA) 
def lca(root, p, q):
    if not root or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root
    return left if left else 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

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.

Binary Search Tree — left < root < right < > < > > 8 3 10 1 6 14 Inorder: 1 → 3 → 6 → 8 → 10 → 14 (sorted!) 
def inorder(node):
    if not 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).

K = 17
depth: list[int] = []
up: list[list[int]] = []


def dfsLift(u: int, p: int, g: list[list[int]]) -> None:
    up[u][0] = p
    for k in range(1, K + 1):
        up[u][k] = -1 if up[u][k - 1] < 0 else up[up[u][k - 1]][k - 1]
    for v in g[u]:
        if v != p:
            depth[v] = depth[u] + 1
            dfsLift(v, u, g)


def lift(u: int, k: int) -> int:
    for i in range(K + 1):
        if k & (1 << i):
            u = -1 if u < 0 else up[u][i]
    return u


def lca(a: int, b: int) -> int:
    if depth[a] < depth[b]:
        a, b = b, a
    a = lift(a, depth[a] - depth[b])
    if a == b:
        return a
    for i in range(K, -1, -1):
        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

Segment Tree — Range Sum for array [1, 3, 5, 7, 2, 4] 22 [0–5] 9 [0–2] 13 [3–5] 4 [0–1] 5 [2] 9 [3–4] 4 [5] 1 [0] 3 [1] 7 [3] 2 [4] array: 1 3 5 7 2 4 index: 0 1 2 3 4 5

Basic Segment Tree (Range Sum Query)

class SegmentTree:
    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)
        self._build(nums, 1, 0, self.n - 1)

    def update(self, index: int, val: int) -> None:
        self._update(1, 0, self.n - 1, index, val)

    def query(self, left: int, right: int) -> int:
        return self._query(1, 0, self.n - 1, left, right)

    def _build(self, node: int, l: int, r: int, nums: list[int]) -> None:
        if l == r:
            self.tree[node] = nums[l]
        else:
            mid = (l + r) // 2
            self._build(node * 2, l, mid, nums)
            self._build(node * 2 + 1, mid + 1, r, nums)
            self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def _update(self, node: int, l: int, r: int, idx: int, val: int) -> None:
        if l == r:
            self.tree[node] = val
        else:
            mid = (l + r) // 2
            if idx <= mid:
                self._update(node * 2, l, mid, idx, val)
            else:
                self._update(node * 2 + 1, mid + 1, r, idx, val)
            self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
        if qr < l or ql > r:
            return 0
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        return self._query(node * 2, l, mid, ql, qr) + self._query(
            node * 2 + 1, mid + 1, r, ql, qr
        )

Segment Tree with Lazy Propagation (Range Update)

class SegmentTreeLazy:
    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self._build(nums, 1, 0, self.n - 1)

    def updateRange(self, left: int, right: int, val: int) -> None:
        self._updateRange(1, 0, self.n - 1, left, right, val)

    def query(self, left: int, right: int) -> int:
        return self._query(1, 0, self.n - 1, left, right)

    def _build(self, node: int, l: int, r: int, nums: list[int]) -> None:
        if l == r:
            self.tree[node] = nums[l]
        else:
            mid = (l + r) // 2
            self._build(node * 2, l, mid, nums)
            self._build(node * 2 + 1, mid + 1, r, nums)
            self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def _push(self, node: int, l: int, r: int) -> None:
        if self.lazy[node] != 0:
            self.tree[node] += self.lazy[node] * (r - l + 1)
            if l != r:
                self.lazy[node * 2] += self.lazy[node]
                self.lazy[node * 2 + 1] += self.lazy[node]
            self.lazy[node] = 0

    def _updateRange(
        self, node: int, l: int, r: int, ql: int, qr: int, val: int
    ) -> None:
        self._push(node, l, r)
        if qr < l or ql > r:
            return
        if ql <= l and r <= qr:
            self.lazy[node] += val
            self._push(node, l, r)
            return
        mid = (l + r) // 2
        self._updateRange(node * 2, l, mid, ql, qr, val)
        self._updateRange(node * 2 + 1, mid + 1, r, ql, qr, val)
        self._push(node * 2, l, mid)
        self._push(node * 2 + 1, mid + 1, r)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
        self._push(node, l, r)
        if qr < l or ql > r:
            return 0
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        return self._query(node * 2, l, mid, ql, qr) + self._query(
            node * 2 + 1, mid + 1, r, ql, qr
        )

Generic Segment Tree Template

from typing import Callable, TypeVar

T = TypeVar("T")


class SegmentTreeGeneric:
    def __init__(
        self,
        arr: list[T],
        identity: T,
        merge: Callable[[T, T], T],
    ):
        self.n = len(arr)
        self.tree = [identity] * (4 * self.n)
        self.identity = identity
        self.merge = merge
        self._build(arr, 1, 0, self.n - 1)

    def update(self, index: int, val: T) -> None:
        self._update(1, 0, self.n - 1, index, val)

    def query(self, left: int, right: int) -> T:
        return self._query(1, 0, self.n - 1, left, right)

    def _build(self, arr: list[T], node: int, l: int, r: int) -> None:
        if l == r:
            self.tree[node] = arr[l]
        else:
            mid = (l + r) // 2
            self._build(arr, node * 2, l, mid)
            self._build(arr, node * 2 + 1, mid + 1, r)
            self.tree[node] = self.merge(self.tree[node * 2], self.tree[node * 2 + 1])

    def _update(self, node: int, l: int, r: int, idx: int, val: T) -> None:
        if l == r:
            self.tree[node] = val
        else:
            mid = (l + r) // 2
            if idx <= mid:
                self._update(node * 2, l, mid, idx, val)
            else:
                self._update(node * 2 + 1, mid + 1, r, idx, val)
            self.tree[node] = self.merge(self.tree[node * 2], self.tree[node * 2 + 1])

    def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> T:
        if qr < l or ql > r:
            return self.identity
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        return self.merge(
            self._query(node * 2, l, mid, ql, qr),
            self._query(node * 2 + 1, mid + 1, r, ql, qr),
        )


# Usage examples:
# Range Sum: SegmentTreeGeneric(arr, 0, lambda a, b: a + b)
# Range Min: SegmentTreeGeneric(arr, float("inf"), min)
# Range Max: SegmentTreeGeneric(arr, float("-inf"), max)

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

def findFirst(node, l: int, r: int, x: int) -> int:
    if node.maxVal < x:
        return -1
    if l == r:
        return l

    mid = l + (r - l) // 2
    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)

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)

class FenwickTree:
    def __init__(self, size: int):
        self.n = size
        self.BIT = [0] * (size + 1)

    # Add delta to element at index i (0-indexed)
    def add(self, i: int, delta: int) -> None:
        i += 1  # Convert to 1-indexed
        while i <= self.n:
            self.BIT[i] += delta
            i += i & -i  # Move to next node

    # Get prefix sum from [0, i] (0-indexed)
    def prefixSum(self, i: int) -> int:
        s = 0
        i += 1  # Convert to 1-indexed
        while i > 0:
            s += self.BIT[i]
            i -= i & -i  # Move to parent
        return s

    # Get range sum from [l, r] (0-indexed)
    def rangeSum(self, l: int, r: int) -> int:
        return self.prefixSum(r) - (self.prefixSum(l - 1) if l > 0 else 0)

Fenwick Tree for Range Sum Query

class NumArray:
    def __init__(self, nums: list[int]):
        self.nums = nums
        self.n = len(nums)
        self.BIT = [0] * (self.n + 1)
        for i in range(self.n):
            self._add(i, nums[i])

    def _add(self, i: int, delta: int) -> None:
        i += 1
        while i <= self.n:
            self.BIT[i] += delta
            i += i & -i

    def _prefixSum(self, i: int) -> int:
        s = 0
        i += 1
        while i > 0:
            s += self.BIT[i]
            i -= i & -i
        return s

    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]
        self.nums[index] = val
        self._add(index, delta)

    def sumRange(self, left: int, right: int) -> int:
        return self._prefixSum(right) - (self._prefixSum(left - 1) if left > 0 else 0)

2D Fenwick Tree

class FenwickTree2D:
    def __init__(self, rows: int, cols: int):
        self.m = rows
        self.n = cols
        self.BIT = [[0] * (cols + 1) for _ in range(rows + 1)]

    def add(self, row: int, col: int, delta: int) -> None:
        row += 1
        col += 1
        i = row
        while i <= self.m:
            j = col
            while j <= self.n:
                self.BIT[i][j] += delta
                j += j & -j
            i += i & -i

    def prefixSum(self, row: int, col: int) -> int:
        s = 0
        row += 1
        col += 1
        i = row
        while i > 0:
            j = col
            while j > 0:
                s += self.BIT[i][j]
                j -= j & -j
            i -= i & -i
        return s

    def rangeSum(self, r1: int, c1: int, r2: int, c2: int) -> int:
        return (
            self.prefixSum(r2, c2)
            - self.prefixSum(r1 - 1, c2)
            - self.prefixSum(r2, c1 - 1)
            + self.prefixSum(r1 - 1, c1 - 1)
        )

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

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.

N = 200000
gH: list[list[int]] = [[] for _ in range(N)]
szH = [0] * N
parH = [0] * N
depH = [0] * N
heavyH = [-1] * N
headH = [0] * N
inH = [0] * N
curT = 0


def dfs1(u: int, p: int) -> int:
    parH[u] = p
    depH[u] = 0 if p == -1 else depH[p] + 1
    szH[u] = 1
    heavyH[u] = -1
    best = 0
    for v in gH[u]:
        if v != p:
            s = dfs1(v, u)
            szH[u] += s
            if s > best:
                best = s
                heavyH[u] = v
    return szH[u]


def dfs2(u: int, h: int) -> None:
    global curT
    headH[u] = h
    inH[u] = curT
    curT += 1
    if heavyH[u] != -1:
        dfs2(heavyH[u], h)
    for v in gH[u]:
        if v != parH[u] and v != heavyH[u]:
            dfs2(v, v)

Note: HLD is rarely required on LeetCode.

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)

More templates