easyTreesPattern: DFS
Total Node Shipments Solution
Problem Statement
Given a tree represented as an adjacency list, calculate the total number of shipments that pass through each node.
Examples
Example 1:
Input:{"adjacencyList":{"1":["2","3"],"2":["1","4"],"3":["1","4"],"4":["2","3"]}}
Output:{"1":4,"2":4,"3":4,"4":4}
Explanation: This example illustrates how to calculate the total number of shipments for each node in a tree structure.
Example 2:
Input:{"adjacencyList":{"1":["2"],"2":["1"]}}
Output:{"1":1,"2":1}
Explanation: This example demonstrates a tree with a single parent-child relationship.
Example 3:
Input:{"adjacencyList":{"1":["2","3"],"2":["1"],"3":["1"]}}
Output:{"1":2,"2":1,"3":1}
Explanation: This example portrays a tree with multiple children for the parent node.
Constraints
- The input tree can be empty, i.e., no nodes.
- Each node in the tree can have multiple children.
- There are no duplicate child nodes for any given parent node.
- The tree is not empty and contains at least one node.
- Each node in the tree is uniquely identified by an integer ID.
Time: O(n) Space: O(n)
A more efficient approach would be to use a recursive DFS, visiting each node only once, to calculate the shipments for each node in O(n) time.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.