What is the time complexity of Shortest Path in a Weighted Tree?

The optimal solution has a time complexity of O(n + q*logn).

What data structures are used to solve Shortest Path in a Weighted Tree?

This problem uses Array, Tree, Depth-First Search, Binary Indexed Tree, Segment Tree. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Shortest Path in a Weighted Tree?

Insight 1: Representing the tree: Using an adjacency list to represent the tree allows efficient traversal and neighbor access. Insight 2: Efficient path calculation: Directly recalculating the shortest path for each query after updates would be inefficient. Instead, use Depth-First Search (DFS) to precompute initial distances and then use a Binary Indexed Tree (BIT) to efficiently track the impact of edge weight changes on subtree distances.

Which companies ask LeetCode 3515. Shortest Path in a Weighted Tree in interviews?

This problem is frequently asked at Juspay.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Shortest Path in a Weighted Tree - LeetCode 3515 Solution

Shortest Path in a Weighted Tree - Complete Solution Guide

Shortest Path in a Weighted Tree is LeetCode problem 3515, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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] = [u i , v i , w i ] indicates an undirected edge from node u i to v i with weight w i . 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 i

Detailed Explanation

The problem requires us to maintain and query shortest path distances from a root node (node 1) to other nodes in a weighted tree. We are given an initial tree structure and a series of queries. There are two types of queries: update the weight of an existing edge, and compute the shortest path distance from the root to a given node. The critical challenge is efficiently handling both edge weight updates and shortest path distance computations after each update.

Solution Approach

The solution uses a combination of Depth-First Search (DFS) and a Binary Indexed Tree (BIT) to efficiently handle edge weight updates and shortest path queries. First, a DFS is performed to precompute the initial shortest path distances from the root to all nodes, along with the depth of each node, start/end times based on the traversal order, and subtree sizes. The edge weights are stored in a hash map for easy access during updates. The start and end times are based on the order nodes are visited during DFS, which allows for range update operations over subtrees. When an edge weight is updated, the difference between the new and old weights (delta) is propagated to all nodes in the subtree rooted at the child node of that edge using the BIT. When a shortest path distance query is received, the initial precomputed distance is combined with the cumulative effect of all edge weight updates affecting the path from the root to the queried node, which is obtained using BIT queries.

Step-by-Step Algorithm

Step 1: Tree Representation: Build an adjacency list representation of the tree using the given `edges` array. Also, create a hash map (edge_map) to store the edge weights for efficient lookup.
Step 2: Depth-First Search (DFS): Perform a DFS traversal of the tree, starting from the root node (node 1). During the traversal, calculate and store the following information for each node:
- parent[node]: The parent of the node in the DFS tree.
- depth[node]: The depth of the node from the root.
- dist[node]: The shortest path distance from the root to the node.
- start_time[node]: The time when the node is first visited during the DFS traversal.
- end_time[node]: The time when the subtree rooted at the node is completely explored.
- subtree_size[node]: The size of the subtree rooted at the node.
Step 3: Binary Indexed Tree (BIT) Initialization: Create a BIT with a size slightly larger than the number of nodes (n+2). This BIT will be used to efficiently track the cumulative effect of edge weight updates on subtree distances.
Step 4: Query Processing: Iterate through the `queries` array and process each query as follows:
- Update Query (q[0] == 1):
- Identify the edge to be updated (u, v).
- Determine the child node of the edge (the deeper node).
- Calculate the delta (difference between the new and old edge weights).
- Update the edge weight in the `edge_map`.
- Use the BIT to add the delta to the subtree rooted at the child node using range update (add delta at start_time[child] and subtract delta at end_time[child] + 1).
- Shortest Path Query (q[0] == 2):
- Retrieve the precomputed distance from the root to the node (x) from `dist[x]`.
- Use the BIT to query the cumulative effect of edge weight updates on the path from the root to the node (x) by querying at `start_time[x]`.
- Add the precomputed distance and the cumulative effect to get the updated shortest path distance.
Step 5: Return Result: After processing all queries, return the array of shortest path distances calculated for the shortest path queries.
Step 6: Free Memory (in C solution) Properly free allocated memory to avoid memory leaks.

Key Insights

Insight 1: Representing the tree: Using an adjacency list to represent the tree allows efficient traversal and neighbor access.
Insight 2: Efficient path calculation: Directly recalculating the shortest path for each query after updates would be inefficient. Instead, use Depth-First Search (DFS) to precompute initial distances and then use a Binary Indexed Tree (BIT) to efficiently track the impact of edge weight changes on subtree distances.
Insight 3: Subtree Updates: When updating an edge weight, the shortest path distances to nodes within the subtree rooted at the *child* node of that edge are affected. The BIT is used to apply these delta changes to the appropriate subtrees. Ordering the DFS traversal according to start and end times simplifies subtree updates.

Complexity Analysis

Time Complexity: O(n + q*logn)

Space Complexity: O(n)

Topics

This problem involves: Array, Tree, Depth-First Search, Binary Indexed Tree, Segment Tree.

Companies

Asked at: Juspay.

Shortest Path in a Weighted Tree | LeetCode 3515

Hard

Array Tree Depth-First Search Binary Indexed Tree Segment Tree

Time: O(n + q*logn)Space: O(n)

Solution Code

Available in:

import java.util.*;

class Solution {
    public int[] treeQueries(int n, int[][] edges, int[][] queries) {
        Map<Integer, List<Pair<Integer, Integer>>> adj = new HashMap<>();
        Map<Pair<Integer, Integer>, Integer> edge_map = new HashMap<>();

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            adj.computeIfAbsent(u, k -> new ArrayList<>()).add(new Pair<>(v, w));
            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(new Pair<>(u, w));
            int u_key = Math.min(u, v);
            int v_key = Math.max(u, v);
            edge_map.put(new Pair<>(u_key, v_key), w);
        }

        int[] parent = new int[n + 1];
        int[] depth = new int[n + 1];
        int[] dist = new int[n + 1];
        int[] start_time = new int[n + 1];
        int[] end_time = new int[n + 1];

        List<Integer> traversal_order = new ArrayList<>();
        Stack<Tuple> stack = new Stack<>();
        stack.push(new Tuple(1, 0, 0, 0)); // (node, parent, depth, current_dist)

        while (!stack.isEmpty()) {
            Tuple tuple = stack.pop();
            int u = tuple.node;
            int p = tuple.parent;
            int d = tuple.depth;
            int cd = tuple.current_dist;
            traversal_order.add(u);

            parent[u] = p;
            depth[u] = d;
            dist[u] = cd;

            List<Tuple> neighbors_to_add = new ArrayList<>();
            if (adj.containsKey(u)) {
                for (Pair<Integer, Integer> neighbor : adj.get(u)) {
                    int v = neighbor.getKey();
                    int w = neighbor.getValue();
                    if (v != p) {
                        neighbors_to_add.add(new Tuple(v, u, d + 1, cd + w));
                    }
                }
            }

            for (int i = neighbors_to_add.size() - 1; i >= 0; i--) {
                stack.push(neighbors_to_add.get(i));
            }
        }

        int time = 0;
        for (int u : traversal_order) {
            time++;
            start_time[u] = time;
        }

        int[] subtree_size = new int[n + 1];
        Arrays.fill(subtree_size, 1);
        for (int i = traversal_order.size() - 1; i >= 0; i--) {
            int u = traversal_order.get(i);
            int p = parent[u];
            if (p != 0) {
                subtree_size[p] += subtree_size[u];
            }
        }

        for (int i = 1; i <= n; i++) {
            end_time[i] = start_time[i] + subtree_size[i] - 1;
        }

        int bit_size = n + 2;
        int[] bit = new int[bit_size];

        class BIT {
            public void add(int i, int delta) {
                while (i < bit_size) {
                    bit[i] += delta;
                    i += i & -i;
                }
            }

            public int query(int i) {
                int s = 0;
                while (i > 0) {
                    s += bit[i];
                    i -= i & -i;
                }
                return s;
            }
        }
        BIT bitInstance = new BIT();

        List<Integer> answerList = new ArrayList<>();
        for (int[] q : queries) {
            if (q[0] == 1) {
                int u = q[1];
                int v = q[2];
                int w_prime = q[3];

                if (depth[u] > depth[v]) {
                    int temp = u;
                    u = v;
                    v = temp;
                }
                int child = v;

                int u_key = Math.min(u, v);
                int v_key = Math.max(u, v);

                int old_w = edge_map.get(new Pair<>(u_key, v_key));
                int delta = w_prime - old_w;
                edge_map.put(new Pair<>(u_key, v_key), w_prime);

                int st = start_time[child];
                int et = end_time[child];
                bitInstance.add(st, delta);
                bitInstance.add(et + 1, -delta);
            } else {
                int x = q[1];
                int initial_dist = dist[x];
                int delta_sum = bitInstance.query(start_time[x]);
                answerList.add(initial_dist + delta_sum);
            }
        }

        int[] answer = new int[answerList.size()];
        for (int i = 0; i < answerList.size(); i++) {
            answer[i] = answerList.get(i);
        }
        return answer;
    }

    static class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            return Objects.equals(key, pair.key) && Objects.equals(value, pair.value);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key, value);
        }
    }
    
    static class Tuple {
        int node, parent, depth, current_dist;
        
        public Tuple(int node, int parent, int depth, int current_dist) {
            this.node = node;
            this.parent = parent;
            this.depth = depth;
            this.current_dist = current_dist;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 3515: Shortest Path in a Weighted Tree - Detailed explanation and solution approaches.

Topics

Array Tree Depth-First Search Binary Indexed Tree Segment Tree

Companies

Juspay

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:3515

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

22 steps

1
Step 1: Tree Representation: Build an adjacency list representation of the tree using the given `edges` array. Also, create a hash map (edge_map) to store the edge weights for efficient lookup.
2
Step 2: Depth-First Search (DFS): Perform a DFS traversal of the tree, starting from the root node (node 1). During the traversal, calculate and store the following information for each node:
3
- parent[node]: The parent of the node in the DFS tree.
4
- depth[node]: The depth of the node from the root.
5
- dist[node]: The shortest path distance from the root to the node.
6
- start_time[node]: The time when the node is first visited during the DFS traversal.
7
- end_time[node]: The time when the subtree rooted at the node is completely explored.
8
- subtree_size[node]: The size of the subtree rooted at the node.
9
Step 3: Binary Indexed Tree (BIT) Initialization: Create a BIT with a size slightly larger than the number of nodes (n+2). This BIT will be used to efficiently track the cumulative effect of edge weight updates on subtree distances.
10
Step 4: Query Processing: Iterate through the `queries` array and process each query as follows:
11
- Update Query (q[0] == 1):
12
- Identify the edge to be updated (u, v).
13
- Determine the child node of the edge (the deeper node).
14
- Calculate the delta (difference between the new and old edge weights).
15
- Update the edge weight in the `edge_map`.
16
- Use the BIT to add the delta to the subtree rooted at the child node using range update (add delta at start_time[child] and subtract delta at end_time[child] + 1).
17
- Shortest Path Query (q[0] == 2):
18
- Retrieve the precomputed distance from the root to the node (x) from `dist[x]`.
19
- Use the BIT to query the cumulative effect of edge weight updates on the path from the root to the node (x) by querying at `start_time[x]`.
20
- Add the precomputed distance and the cumulative effect to get the updated shortest path distance.
21
Step 5: Return Result: After processing all queries, return the array of shortest path distances calculated for the shortest path queries.
22
Step 6: Free Memory (in C solution) Properly free allocated memory to avoid memory leaks.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n + q*logn)

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The DFS explores each node and edge once, resulting in O(n) time. The BIT's `add` and `query` operations involve traversing the tree-like structure of the BIT, which takes O(logn) time, where n is the size of the input (number of nodes). The various arrays allocated contribute to the O(n) space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Dijkstra's Algorithm

Dijkstra's algorithm could be used to recalculate the shortest path from the root to a node after each edge weight update. This involves running Dijkstra's from node 1 for each 'compute' query.

Time: O(q * (n + m) * log(n)), where q is the number of queries, n is the number of nodes, and m is the number of edges (m = n-1). Dijkstra's takes O((n+m)log n) time.Space: O(n), for the distance array and priority queue in Dijkstra's.

Trade-offs: Dijkstra's is simpler to implement but less efficient than the BIT approach for a large number of queries, especially update queries. Suitable if the number of queries is small, or if the update frequency is low. This solution would likely timeout for large datasets.

Floyd-Warshall Algorithm

Floyd-Warshall computes shortest paths between all pairs of nodes. After each edge update, run the algorithm to get an updated all-pairs shortest path.

Time: O(q * n^3), where q is the number of queries and n is the number of nodes. Floyd-Warshall takes O(n^3) to calculate shortest paths between all pairs.Space: O(n^2), for the adjacency matrix to store distances between all pairs of nodes.

Trade-offs: Floyd-Warshall's is extremely inefficient for this problem, given its cubic time complexity. It's not appropriate when n is large, and the number of queries is significant.

✨

Key Insights

1Insight 1: Representing the tree: Using an adjacency list to represent the tree allows efficient traversal and neighbor access.
2Insight 2: Efficient path calculation: Directly recalculating the shortest path for each query after updates would be inefficient. Instead, use Depth-First Search (DFS) to precompute initial distances and then use a Binary Indexed Tree (BIT) to efficiently track the impact of edge weight changes on subtree distances.
3Insight 3: Subtree Updates: When updating an edge weight, the shortest path distances to nodes within the subtree rooted at the *child* node of that edge are affected. The BIT is used to apply these delta changes to the appropriate subtrees. Ordering the DFS traversal according to start and end times simplifies subtree updates.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Tree with only two nodes. The solution correctly handles the update and query operations when the tree is very small.
Edge case 2: Edge weight updates that result in negative edge weights. The problem constraints prevent negative edge weights, simplifying the shortest path calculation.
Edge case 3: Query for the root node (node 1). The shortest path distance from the root to itself is always 0. The solution needs to account for BIT updates to paths including the root, hence we initialize dist[1] = 0.
Edge case 4: Updating an edge weight multiple times consecutively. The BIT is able to correctly reflect the cumulative updates for all the nodes.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to consider the subtree update. Updating an edge weight directly affects the shortest path distances to all nodes in the subtree rooted at the child node.

✗Common mistake 2: Inefficiently recalculating the shortest path for each query. This would result in exceeding the time limit, especially for a large number of queries.

✗Common mistake 3: Incorrect BIT implementation (off-by-one errors, incorrect update/query logic). Pay close attention to the BIT implementation to ensure correct results.

✗Common mistake 4: Forgetting to free the allocated memory in C. This will cause memory leaks.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Network routing: In a network, nodes represent routers and edges represent connections between them. Edge weights represent the cost of sending data across a connection (e.g., latency, bandwidth). The algorithm can be used to efficiently compute and update shortest paths between routers when network conditions change.

🏦Real-world scenario 2: Transportation networks: Representing cities as nodes and roads as edges with travel times as weights. Updates to the travel times (due to traffic, road closures) can be efficiently reflected using this approach, and shortest travel times can be queried in real time.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 4, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

What is the difference between DFS and BFS for trees?

DFS (using recursion or stack) explores depth-first, useful for path-finding and backtracking problems. BFS (using queue) explores level-by-level, ideal for finding shortest paths or processing nodes by depth. Choose based on whether level information matters.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Shortest Path in a Weighted Tree"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether tree techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?