DSA & Algorithms
Part 12 of 16 · DSA Advanced & Company FavoritesTrees Advanced - LCA, Rerooting, Path aggregates
LCA binary lifting intuition, rerooting DP, and path aggregates on trees.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The tree is static and you answer many path questions
Prefer
Lift parents, or reroot a subtree DP
Binary lifting answers LCA in log n after n log n preprocess.
- Jump the deeper node up first.
- Reroot moves the root without recomputing from scratch.
- Path sums are not subtree sums.
Alternative
DFS from the root for every query
That is correct and too slow for q queries.
- You lift without equalizing depth.
- You reroot and forget the parent contribution.
- You store only children and lose the upward edge.
Preprocess, then answer
Lifting for LCA. One reroot pass for subtree DP.
- 1
Root the tree
Pick a root and store parents. - 2
Binary lift
parent[k][v] jumps 2^k. - 3
Or reroot
Move the answer from parent to child in one pass.
Overview
LCA binary lifting intuition, rerooting DP, and path aggregates on trees.
When companies ask this
Recognition cues: lowest common ancestor; distance queries; reroot to compute answer for every root; path sum / max path variants beyond binary tree.
Mental model
Flow
- 1
1. Root the tree
- next2. Binary lift parents
- 2
2. Binary lift parents
- next3. LCA by jumping
- 3
3. LCA by jumping
- next4. Reroot a downward DP
- 4
4. Reroot a downward DP
Lesson map
Trees Advanced - LCA, Rerooting, Path aggregates
LCA binary lifting intuition, rerooting DP, and path aggregates on trees.
Architecture. 1. Root the tree Ready. 2. Binary lift parents Ready. 3. LCA by jumping Ready. 4. Reroot a downward DP Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Root["1. Root the tree Ready"] Lift["2. Binary lift parents Ready"] LCA["3. LCA by jumping Ready"] Reroot["4. Reroot a downward DP Ready"] Root -->|continues| Lift Lift -->|continues| LCA LCA -->|continues| Reroot
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- Binary lifting preprocess O(n log n), query O(log n).
- Reroot usually O(n).
- Pitfalls: not lifting deeper node first; wrong size when rerooting. Deep trees raise
sys.setrecursionlimitin the template, or the walk becomes an explicit stack.
Interviewer traps
LeetCode drill (real problems)
- Lowest Common Ancestor of a Binary Tree
- Lowest Common Ancestor of a Binary Search Tree
- Binary Tree Maximum Path Sum
- Sum of Distances in Tree
- Diameter of Binary Tree
- Path Sum III
- Kth Ancestor of a Tree Node
- Minimum Height Trees
- All Nodes Distance K in Binary Tree
YouTube
Interview Q&A
Binary tree LCA?
Answer
If p and q in different sides, root is LCA.
Dist via LCA?
Answer
depth[a]+depth[b]-2*depth[lca].
Reroot idea?
Answer
For sum of distances: ans[child] = ans[parent] - size[child] + (n - size[child]); other reroot problems need their own transition (often prefix/suffix merges).
Binary lifting?
Answer
up[v][k] = 2^k-th parent.
Max path sum?
Answer
Gain from children; update global; return single-arm.
Related wave-1?
Answer
trees-dfs, BST, dp-advanced.
Kth ancestor?
Answer
Binary lifting jumps.
MHT?
Answer
Peel leaves; centroids of tree.