Skip to content

Fix the Structure

On the previous page, every problem lived in a flat array. Fix a value, look it up in a map, move on. Clean and simple.

Trees aren't flat. They branch. They have parent-child relationships, subtree sizes, paths that bend at turning points. But the fixing mindset works exactly the same way — you just have to pick the right thing to fix.

This page covers three tree-fixing patterns, plus one array technique (monotonic stack) that feels similar in spirit. By the end, you'll have 10 tree problems to practice.

Prerequisites: DFS on trees, basic recursion, stacks.

Pattern 1: Fix the Edge

This is the most elegant tree trick. Instead of asking "which paths exist?" you flip the question: for each edge, how many paths cross it?

The Idea

Picture a tree with \(N\) nodes. Pick any edge and imagine cutting it with scissors. The tree splits into two pieces — one of size \(S\), the other of size \(N - S\).

Now, any path that starts in the left piece and ends in the right piece must cross this edge. How many such paths? Every node in the left piece can pair with every node in the right piece:

\[\text{Paths crossing this edge} = S \times (N - S)\]

That's it. No path-finding, no BFS, no complicated bookkeeping. Just count subtree sizes.

Teaching Example: Count All Node Pairs Across Edges

You want the total count of all simple paths (pairs of nodes) in a tree.

Fix: Each edge, one at a time. Calculate: \(S \times (N - S)\) for each edge, then sum them all up.

How do you get subtree sizes? A single DFS that returns the size of each subtree. When you're at node u and you've just computed the subtree size of child v, the edge between u and v splits the tree into childSize vs N - childSize.

long long totalNodes;
long long ans = 0;

long long dfs(int u, int parent, const vector<vector<int>>& adj) {
    long long sz = 1;
    for (int v : adj[u]) {
        if (v == parent) continue;
        long long childSz = dfs(v, u, adj);

        // FIX: the edge between u and v
        // CALCULATE: nodes in subtree × nodes outside subtree
        ans += childSz * (totalNodes - childSz);

        sz += childSz;
    }
    return sz;
}

One DFS. \(O(N)\). And you've counted every pair of nodes along with which edges their path crosses.

Why This Pattern is Powerful

The "fix the edge" trick turns path-counting problems into subtree-size problems. And subtree sizes are trivially computable with a single DFS. You'll see this pattern in:

  • Max Product of Splitted Binary Tree — instead of counting pairs, you want the product of the two subtree sums
  • Distribute Coins — instead of counting pairs, you want the flow (excess coins) across each edge
  • Sum of Distances in Tree — you fix the edge and compute how re-rooting affects the distance sum

Each problem puts a different "lens" on the same fundamental operation: cut an edge, look at what's on each side.

Pattern 2: Fix the Node (Turning Point)

Some tree problems ask about paths. The path goes up from some node, through an ancestor, and back down. The ancestor where the path "bends" is the turning point.

Fix the turning point. Calculate the left arm and the right arm.

Teaching Example: Longest Univalue Path

Problem: Find the longest path in a binary tree where every node has the same value.

The path might go left-down from some node and right-down from the same node. That node is the turning point.

For each node, your DFS returns "the longest arm extending downward through matching values." At each node, you check: does my left child match me? Does my right child match me? If yes, extend that arm by 1.

The path through this node = left arm + right arm. The value returned to my parent = the longer of the two arms (because a path through my parent can only use one direction from me).

int ans = 0;
int dfs(TreeNode* root) {
    if (!root) return 0;
    int l = dfs(root->left), r = dfs(root->right);
    int leftArm = 0, rightArm = 0;
    if (root->left && root->left->val == root->val) leftArm = l + 1;
    if (root->right && root->right->val == root->val) rightArm = r + 1;

    // FIX: this node as the turning point
    // CALCULATE: path through here = left arm + right arm
    ans = max(ans, leftArm + rightArm);

    return max(leftArm, rightArm);  // only one arm goes up to parent
}

This "return one arm, update answer with both arms" pattern shows up constantly. You'll use it in diameter problems, path sum problems, and the coin distribution problem.

The Key Distinction

In the DFS, there are two different things:

  1. The answer at this node — uses both children (left arm + right arm)
  2. What you return to the parent — uses only the better child (because a path can't fork)

This trips people up. If you return leftArm + rightArm to the parent, you're saying "the path forks at me AND continues through my parent," which isn't a valid path. Always return the single best arm.

Pattern 3: Fix the Path (Carry State Downward)

The simplest tree pattern. As you DFS from root to leaves, carry some accumulated state — the running sum, the maximum so far, the current number being formed. At each node, you fix the path from root to here and use the accumulated state to make a decision.

Teaching Example: Count Good Nodes

Problem: Count nodes where the node's value is greater than or equal to every value on the path from the root to that node.

As you walk down, carry the maximum value seen so far. At each node, compare.

int count = 0;
void dfs(TreeNode* root, int maxSoFar) {
    if (!root) return;
    // FIX: the path from root to here
    // CALCULATE: is this node "good"?
    if (root->val >= maxSoFar) count++;
    maxSoFar = max(maxSoFar, root->val);
    dfs(root->left, maxSoFar);
    dfs(root->right, maxSoFar);
}

Dead simple. But notice it's still fixing — you're fixing the path, and the carried state tells you everything you need to make a decision at this node.

Sum Root to Leaf Numbers uses the same pattern, just carrying val * 10 + node->val instead of a maximum.

Pattern 4: Prefix Sums on Trees

Remember how prefix sums turned subarray problems into point problems on arrays? The same trick works on trees — but with a twist.

Teaching Example: Path Sum III

Problem: Count paths in a binary tree that sum to a target. The path can start and end anywhere (doesn't have to be root-to-leaf).

On an array, you'd keep a running prefix sum and check if prefix - target exists in a hash map. On a tree, you do the same thing, except the "array" is the path from root to the current node.

The twist: when you backtrack in the DFS, you have to undo the prefix sum entry. On an array you never backtrack, but tree DFS explores one branch and then comes back to try another. If you don't clean up, prefix sums from the left subtree leak into the right subtree.

unordered_map<long, int> seen;
int count = 0;

void dfs(TreeNode* root, int target, long prefix) {
    if (!root) return;
    prefix += root->val;

    // FIX: path ending at this node
    // CALCULATE: how many path-starts give us the target sum?
    if (seen.count(prefix - target))
        count += seen[prefix - target];

    seen[prefix]++;
    dfs(root->left, target, prefix);
    dfs(root->right, target, prefix);
    seen[prefix]--;  // BACKTRACK: undo before returning to parent
}

// Call with: seen[0] = 1; dfs(root, target, 0);

That seen[prefix]-- line is the whole game. Without it, you'd count paths that jump between branches — which aren't real paths in a tree.

If you understood "Subarray Sum Equals K" from Page 2, this is the same idea with one extra line.

Bonus: Fix the Element (Monotonic Stack)

This one's on arrays, not trees, but it shares the same "contribution" spirit as the tree patterns. Instead of asking "what's the minimum of every subarray?" you ask: for each element, how many subarrays is it the minimum of?

The Idea

Fix element A[i] and assume it's the minimum of some subarray. How far left can the subarray extend before hitting something smaller? How far right?

  • \(L\) = distance to the Previous Less Element (PLE)
  • \(R\) = distance to the Next Less Element (NLE)

Any subarray starting in the range \([i - L + 1, i]\) and ending in \([i, i + R - 1]\) has A[i] as its minimum. That's \(L \times R\) subarrays.

\[\text{Contribution of } A[i] = A[i] \times L \times R\]

A monotonic stack finds PLE and NLE for all elements in \(O(N)\).

int sumSubarrayMins(vector<int>& arr) {
    int n = arr.size();
    vector<int> left(n), right(n);
    stack<int> s;

    // Find PLE (Previous Less Element) distances
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && arr[s.top()] >= arr[i]) s.pop();
        left[i] = s.empty() ? i + 1 : i - s.top();
        s.push(i);
    }

    while (!s.empty()) s.pop();

    // Find NLE (Next Less Element) distances
    for (int i = n - 1; i >= 0; --i) {
        while (!s.empty() && arr[s.top()] > arr[i]) s.pop();
        right[i] = s.empty() ? n - i : s.top() - i;
        s.push(i);
    }

    long long ans = 0, mod = 1e9 + 7;
    for (int i = 0; i < n; ++i) {
        // FIX: element arr[i] as the subarray minimum
        // CALCULATE: contribution = value × left range × right range
        ans = (ans + (long long)arr[i] * left[i] * right[i]) % mod;
    }
    return ans;
}

Why >= in the PLE pass but > in the NLE pass? To handle duplicate values. If two elements are equal, one of them "owns" the subarrays where they're both the minimum. Using strict on one side and non-strict on the other avoids double-counting.

This technique is sometimes called contribution technique — and it's the same spirit as fixing an edge in a tree. You're saying: "Let me fix this one piece. How much does it contribute to the total answer?"

Practice Set

Problems are ordered from easiest to hardest within each tier.

Warm-Up (DFS with Carried State)

  1. 129. Sum Root to Leaf Numbers — Fix path, carry val * 10 + node
  2. 1448. Count Good Nodes in Binary Tree — Fix path, carry max so far

Core Practice (Edge Fixing & Turning Points)

  1. 1339. Max Product of Splitted Binary Tree — Fix edge, Calc subtree_sum × (total - subtree_sum)
  2. 979. Distribute Coins in Binary Tree — Fix edge, Calc flow = coins - nodes
  3. 687. Longest Univalue Path * — Fix turning point, Calc left arm + right arm
  4. 2673. Make Costs of Paths Equal — Fix subtree, Calc diff between children

Harder (Re-rooting, LCA, Prefix on Trees)

  1. 437. Path Sum III * — Fix path end, prefix sum with backtracking
  2. 1530. Number of Good Leaf Nodes Pairs — Fix LCA, Calc left dist + right dist
  3. 2049. Count Nodes With Highest Score — Fix node removal, Calc product of component sizes
  4. 834. Sum of Distances in Tree — Fix root, re-root to all nodes (hardest on this page)

Solutions

Warm-Up

11. Sum Root to Leaf Numbers

Carry the number being formed as you walk down. When you hit a leaf, add it to the total.

int ans = 0;
void dfs(TreeNode* root, int val) {
    if (!root) return;
    // FIX: the path ending at current node
    // CALCULATE: update current number
    val = val * 10 + root->val;
    if (!root->left && !root->right) ans += val;
    dfs(root->left, val);
    dfs(root->right, val);
}
int sumNumbers(TreeNode* root) {
    dfs(root, 0);
    return ans;
}
12. Count Good Nodes in Binary Tree

Carry the max seen on the path from root. A node is "good" if it's >= that max.

int count = 0;
void dfs(TreeNode* root, int maxVal) {
    if (!root) return;
    // FIX: path from root to here
    // CALCULATE: is current >= max seen so far?
    if (root->val >= maxVal) count++;
    maxVal = max(maxVal, root->val);
    dfs(root->left, maxVal);
    dfs(root->right, maxVal);
}
int goodNodes(TreeNode* root) {
    dfs(root, root->val);
    return count;
}

Core Practice

13. Max Product of Splitted Binary Tree

First pass computes the total sum. Second pass tries every possible edge cut and tracks the maximum product of the two pieces.

long long total = 0, ans = 0;
long long subtreeSum(TreeNode* root) {
    if (!root) return 0;
    long long s = root->val + subtreeSum(root->left) + subtreeSum(root->right);
    // FIX: the edge above this subtree
    // CALCULATE: product of subtree sum and remainder
    if (total != 0) ans = max(ans, s * (total - s));
    return s;
}
int maxProduct(TreeNode* root) {
    total = subtreeSum(root);  // first pass: get total
    subtreeSum(root);          // second pass: find max product
    return ans % (int)(1e9 + 7);
}

Why two passes? In the first pass, you don't know total yet, so you can't compute total - subtreeSum. After the first pass gives you total, the second pass can compute both sides of every cut.

14. Distribute Coins in Binary Tree

Each node needs exactly 1 coin. The DFS returns the "excess" of each subtree (coins minus nodes). The flow across each edge is the absolute value of that excess.

int moves = 0;
int dfs(TreeNode* root) {
    if (!root) return 0;
    int l = dfs(root->left), r = dfs(root->right);
    // FIX: edge connecting this node to parent
    // CALCULATE: flow = |excess from left| + |excess from right|
    moves += abs(l) + abs(r);
    return root->val - 1 + l + r;  // excess: coins minus 1 (for self)
}
int distributeCoins(TreeNode* root) {
    dfs(root);
    return moves;
}

The return value root->val - 1 + l + r is the net excess: this node's coins, minus 1 for itself, plus whatever excess came from its children. If it's positive, coins flow up to the parent. If negative, coins flow down from the parent.

15. Longest Univalue Path

Fix each node as a potential turning point. Return the longer arm to the parent.

int ans = 0;
int dfs(TreeNode* root) {
    if (!root) return 0;
    int l = dfs(root->left), r = dfs(root->right);
    int pl = 0, pr = 0;
    if (root->left && root->left->val == root->val) pl = l + 1;
    if (root->right && root->right->val == root->val) pr = r + 1;
    // FIX: the root as the turning point
    // CALCULATE: path through root = left arm + right arm
    ans = max(ans, pl + pr);
    return max(pl, pr);
}
int longestUnivaluePath(TreeNode* root) {
    dfs(root);
    return ans;
}
16. Make Costs of Paths Equal in a Binary Tree

Work bottom-up. At each internal node, the two children should contribute equally to path cost. The difference between them is the minimum increment needed. Propagate the larger value upward.

int minIncrements(int n, vector<int>& cost) {
    int ans = 0;
    for (int i = n / 2 - 1; i >= 0; --i) {
        // FIX: subtree rooted at i
        // CALCULATE: difference between children = cost to equalize
        int l = cost[2 * i + 1], r = cost[2 * i + 2];
        ans += abs(l - r);
        cost[i] += max(l, r);  // propagate the max upward
    }
    return ans;
}

This works because the tree is given as a 1-indexed array (perfect binary tree). Children of node i are at 2i+1 and 2i+2. Processing from the last internal node backward is a clean bottom-up traversal.

Harder

17. Path Sum III

Prefix sums on a tree path, with backtracking to undo when you leave a branch.

unordered_map<long, int> seen;
int count = 0;
void dfs(TreeNode* root, int target, long prefix) {
    if (!root) return;
    prefix += root->val;
    // FIX: path ending at this node
    // CALCULATE: prefix sums that give target
    if (seen.count(prefix - target))
        count += seen[prefix - target];
    seen[prefix]++;
    dfs(root->left, target, prefix);
    dfs(root->right, target, prefix);
    seen[prefix]--;  // backtrack
}
int pathSum(TreeNode* root, int targetSum) {
    seen[0] = 1;
    dfs(root, targetSum, 0);
    return count;
}
18. Number of Good Leaf Nodes Pairs

Fix each node as a potential LCA. Collect distances of leaves in left and right subtrees. Count pairs where left_dist + right_dist <= d.

int ans = 0;
vector<int> dfs(TreeNode* root, int d) {
    if (!root) return {};
    if (!root->left && !root->right) return {1};  // leaf at distance 1
    auto l = dfs(root->left, d), r = dfs(root->right, d);
    // FIX: this node as the LCA
    // CALCULATE: pairs from left × right with total distance <= d
    for (int i : l)
        for (int j : r)
            if (i + j <= d) ans++;
    vector<int> res;
    for (int i : l) if (i + 1 < d) res.push_back(i + 1);
    for (int j : r) if (j + 1 < d) res.push_back(j + 1);
    return res;
}
int countPairs(TreeNode* root, int distance) {
    dfs(root, distance);
    return ans;
}

The return value is a list of leaf distances from this node. Each distance gets +1 as it bubbles up. We prune distances that are already >= d since they can't form a valid pair.

19. Count Nodes With Highest Score

Remove a node and the tree splits into up to 3 components: left child's subtree, right child's subtree, and everything above. The "score" is the product of their sizes.

int countHighestScoreNodes(vector<int>& parents) {
    int n = parents.size();
    vector<vector<int>> children(n);
    for (int i = 1; i < n; ++i)
        children[parents[i]].push_back(i);

    long long maxScore = 0;
    int cnt = 0;

    function<int(int)> dfs = [&](int u) -> int {
        int sz = 1;
        long long score = 1;
        for (int v : children[u]) {
            int childSz = dfs(v);
            score *= childSz;
            sz += childSz;
        }
        // FIX: node u (remove it)
        // CALCULATE: product of all component sizes
        if (n - sz > 0) score *= (n - sz);  // the "above" component
        if (score > maxScore) { maxScore = score; cnt = 1; }
        else if (score == maxScore) cnt++;
        return sz;
    };

    dfs(0);
    return cnt;
}

The n - sz term is the component above node u — everything that's not in u's subtree. For the root, this is 0, so we skip multiplying by it.

20. Sum of Distances in Tree

This is a classic re-rooting problem. First compute the answer for node 0 as root. Then shift the root to each child using the relationship: moving the root from u to v means nodes in v's subtree get 1 closer, and all other nodes get 1 farther.

vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }

    vector<int> ans(n, 0), cnt(n, 1);  // cnt[u] = subtree size

    // Pass 1: compute subtree sizes and answer for root 0
    function<void(int, int)> dfs1 = [&](int u, int p) {
        for (int v : adj[u]) {
            if (v == p) continue;
            dfs1(v, u);
            cnt[u] += cnt[v];
            ans[u] += ans[v] + cnt[v];
        }
    };

    // Pass 2: re-root from parent to child
    function<void(int, int)> dfs2 = [&](int u, int p) {
        for (int v : adj[u]) {
            if (v == p) continue;
            // FIX: the edge between u and v (re-rooting)
            // CALCULATE: v's answer from u's answer
            ans[v] = ans[u] - cnt[v] + (n - cnt[v]);
            dfs2(v, u);
        }
    };

    dfs1(0, -1);
    dfs2(0, -1);
    return ans;
}

The re-rooting formula ans[v] = ans[u] - cnt[v] + (n - cnt[v]) says: moving the root from u to v means cnt[v] nodes (in v's subtree) each get 1 closer (subtract cnt[v]), and n - cnt[v] nodes (outside v's subtree) each get 1 farther (add n - cnt[v]).

This is the hardest problem on this page. If the re-rooting formula doesn't click immediately, draw a small tree (5-6 nodes), compute the answer for the root by hand, then manually verify the formula for one child. Seeing the numbers move makes it real.

What's Next

The final page — Fix the Group — takes fixing into graphs. You'll fix connected components, use the complement trick at graph scale, and tackle absolute value problems. It also includes the combinatorics bonus problems.