Shortest Path in a Weighted Tree

Shortest Path in a Weighted Tree

What is this problem about?

The Shortest Path in a Weighted Tree interview question asks you to process a sequence of queries on a weighted tree: either update the weight of an edge or compute the distance between two nodes. The path between any two nodes in a tree is unique — it goes through their lowest common ancestor (LCA). Efficiently answering distance queries after weight updates requires Euler tour flattening combined with a segment tree or binary indexed tree.

Why is this asked in interviews?

Juspay asks this HARD problem because it combines advanced tree data structures: LCA computation (using Euler tour or binary lifting) with a segment tree/BIT for range sum queries and point updates. Updating edge weights and querying path distances in O(log^2 n) per operation is a non-trivial skill that appears in competitive programming and systems requiring efficient hierarchical data traversal.

Algorithmic pattern used

The pattern is Euler tour + segment tree with LCA. Perform an Euler tour of the tree to flatten it into an array where each node's subtree is a contiguous range. Represent edge weights as node weights (assign edge weight to the deeper node). For a distance query (u, v): find LCA(u, v) using binary lifting. Distance = depth[u] + depth[v] - 2×depth[LCA]. When an edge weight is updated, update the corresponding node's value in the segment tree. Use a segment tree for range sum queries to compute path weight sums.

Example explanation

Tree: 1-2 (weight 3), 2-3 (weight 5), 2-4 (weight 2).

Query: distance(1, 3) = weight(1-2) + weight(2-3) = 3 + 5 = 8. Update: weight of edge 1-2 to 7. Query: distance(1, 3) = 7 + 5 = 12.

With LCA: LCA(1,3) = 1 (assuming rooted at 1). dist = depth[3] - depth[1] using segment tree path sum.

Common mistakes candidates make

• Using DFS for each distance query — O(n) per query is too slow; preprocess with LCA.
• Not handling the Euler tour correctly — the entry/exit times must correctly represent subtree ranges.
• Forgetting that edge weights are stored on the deeper node (child node) to enable point updates.
• Using brute-force LCA (climb one node at a time) instead of binary lifting O(log n) LCA.

Interview preparation tip

For the Shortest Path in a Weighted Tree coding problem, the segment tree DFS binary indexed tree interview pattern with LCA is the advanced approach. This problem requires combining three advanced techniques: Euler tour for flattening, binary lifting for LCA, and a segment tree for range queries. Juspay interviewers expect familiarity with each component independently before combining them. Practice each component separately — Euler tour on trees, binary lifting LCA, and range-sum segment trees — then integrate them for this problem class.