Skip to main content
Talentd

Shortest Path in a Weighted Tree - Solution & Explanation

HardArrayTreeDepth-First SearchBinary Indexed Tree5 min readAsked at: Juspay
Practice this problem

Problem Statement

You are given an integer n and an undirected, weighted tree rooted at node 1 with n nodes numbered from 1 to n. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi, wi] indicates an undirected edge from node ui to vi with weight wi.

You are also given a 2D integer array queries of length q, where each queries[i] is either:

  • [1, u, v, w'] – Update the weight of the edge between nodes u and v to w', where (u, v) is guaranteed to be an edge present in edges.
  • [2, x] – Compute the shortest path distance from the root node 1 to node x.

Return an integer array answer, where answer[i] is the shortest path distance from node 1 to x for the ith query of [2, x].

 

Example 1:

Input: n = 2, edges = [[1,2,7]], queries = [[2,2],[1,1,2,4],[2,2]]

Output: [7,4]

Explanation:

  • Query [2,2]: The shortest path from root node 1 to node 2 is 7.
  • Query [1,1,2,4]: The weight of edge (1,2) changes from 7 to 4.
  • Query [2,2]: The shortest path from root node 1 to node 2 is 4.

Example 2:

Input: n = 3, edges = [[1,2,2],[1,3,4]], queries = [[2,1],[2,3],[1,1,3,7],[2,2],[2,3]]

Output: [0,4,2,7]

Explanation:

  • Query [2,1]: The shortest path from root node 1 to node 1 is 0.
  • Query [2,3]: The shortest path from root node 1 to node 3 is 4.
  • Query [1,1,3,7]: The weight of edge (1,3) changes from 4 to 7.
  • Query [2,2]: The shortest path from root node 1 to node 2 is 2.
  • Query [2,3]: The shortest path from root node 1 to node 3 is 7.

Example 3:

Input: n = 4, edges = [[1,2,2],[2,3,1],[3,4,5]], queries = [[2,4],[2,3],[1,2,3,3],[2,2],[2,3]]

Output: [8,3,2,5]

Explanation:

  • Query [2,4]: The shortest path from root node 1 to node 4 consists of edges (1,2), (2,3), and (3,4) with weights 2 + 1 + 5 = 8.
  • Query [2,3]: The shortest path from root node 1 to node 3 consists of edges (1,2) and (2,3) with weights 2 + 1 = 3.
  • Query [1,2,3,3]: The weight of edge (2,3) changes from 1 to 3.
  • Query [2,2]: The shortest path from root node 1 to node 2 is 2.
  • Query [2,3]: The shortest path from root node 1 to node 3 consists of edges (1,2) and (2,3) with updated weights 2 + 3 = 5.

 

Constraints:

  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[i] == [ui, vi, wi]
  • 1 <= ui, vi <= n
  • 1 <= wi <= 104
  • The input is generated such that edges represents a valid tree.
  • 1 <= queries.length == q <= 105
  • queries[i].length == 2 or 4
    • queries[i] == [1, u, v, w'] or,
    • queries[i] == [2, x]
    • 1 <= u, v, x <= n
    • (u, v) is always an edge from edges.
    • 1 <= w' <= 104

Approach Overview

Problem Overview: You are given a weighted tree and need to compute the shortest path distance between nodes. Because a tree contains exactly one simple path between any two nodes, the task reduces to efficiently calculating distances along that path, often across many queries.

Approach 1: DFS per Query (Brute Force) (Time: O(n) per query, Space: O(n))

The most direct strategy runs a DFS from the source node until the destination node is reached. While traversing, accumulate edge weights and stop once the target appears. Since a tree has no cycles, the traversal visits each node at most once. This works for a small number of queries but becomes expensive when the query count grows because each query can traverse the entire tree.

Approach 2: Prefix Distance + Lowest Common Ancestor (Time: O(n log n) preprocessing, O(log n) per query, Space: O(n log n))

Precompute the distance from a chosen root to every node using a single DFS. Store dist[node] as the total weight from the root. The distance between two nodes u and v can then be computed using their Lowest Common Ancestor: dist[u] + dist[v] - 2 * dist[lca(u,v)]. LCA queries are answered using binary lifting tables built during preprocessing. This reduces repeated traversal and turns path distance queries into constant arithmetic plus an LCA lookup. See related techniques in Tree and Depth-First Search.

Approach 3: Euler Tour + Binary Indexed Tree / Segment Tree (Time: O((n + q) log n), Space: O(n))

If the problem includes edge weight updates or dynamic queries, combine an Euler tour with a range data structure. Flatten the tree into an array using entry/exit times from DFS. Store edge contributions in a Binary Indexed Tree or Segment Tree. Distance from root to any node becomes a prefix query on the flattened structure, while updates propagate with log n modifications. Path distance queries still use the LCA formula but fetch prefix sums dynamically. This approach appears frequently in advanced tree problems involving updates. See Binary Indexed Tree and Segment Tree.

Recommended for interviews: Start by explaining the DFS brute force to show understanding of tree traversal. Interviewers typically expect the LCA + prefix distance solution because it answers queries in O(log n) after preprocessing. If the problem introduces updates, extending the design with Euler tour and Fenwick/Segment Tree demonstrates strong tree algorithm skills.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS per QueryO(n) per queryO(n)Small trees or very few queries
Prefix Distance + LCA (Binary Lifting)O(n log n) preprocessing, O(log n) queryO(n log n)Standard solution for many shortest path queries in a static tree
Euler Tour + Fenwick / Segment TreeO((n + q) log n)O(n)When edge weights can change or queries require dynamic updates

Video Solution

L-9. Shortest Path In a Weighted Tree • Segment Tree Series • Leetcode Biweekly 154 Contest • ET+LP • Why Not DP [By Piyush Raj] • 661 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Shortest Path in a Weighted Tree easy or hard?
This problem is generally rated Hard because it combines multiple concepts: tree traversal, LCA preprocessing, and sometimes advanced data structures like Fenwick Trees or Segment Trees. Efficient handling of many queries is the main challenge.
Shortest Path in a Weighted Tree Python/Java solution
Typical implementations build an adjacency list, run DFS to compute depth and prefix distance arrays, and precompute LCA ancestors. The query formula dist[u] + dist[v] - 2 * dist[lca(u,v)] works the same in Python, Java, C++, and Go with O(log n) query time.
How to solve Shortest Path in a Weighted Tree in O(n)?
A single DFS can compute distances from the root to all nodes in O(n). If you only need distances from that root, each result becomes a direct lookup. For arbitrary node pairs, combine those prefix distances with an LCA computation to keep query time efficient.
What is the best approach for Shortest Path in a Weighted Tree?
The most practical approach is prefix distance with Lowest Common Ancestor (LCA). Precompute the distance from the root to every node using DFS, then answer queries using dist[u] + dist[v] - 2 * dist[lca(u,v)]. With binary lifting, preprocessing takes O(n log n) and each query runs in O(log n).
Is Shortest Path in a Weighted Tree asked at Google/Amazon/Meta?
Tree distance and LCA-style problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often include computing distances between nodes, supporting updates, or handling large query volumes efficiently.
What data structure is used in Shortest Path in a Weighted Tree?
Common structures include adjacency lists for the tree, binary lifting tables for LCA computation, and sometimes Binary Indexed Trees or Segment Trees when edge weights or node values must be updated dynamically.
What is the time complexity of Shortest Path in a Weighted Tree?
Using the LCA-based solution, preprocessing requires O(n log n) time to build ancestor tables and compute root distances. Each shortest path query is answered in O(log n). A brute-force DFS solution takes O(n) per query.

Ready to solve this problem?

Practice Shortest Path in a Weighted Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays