Prerequisites :- Trees, DFS.
Problem :- Given a binary tree with N nodes where the ith node has a value Vi associated to it. The root of the tree is node 1.
Note that Vi is a single digit from 0 to 9.
A branch is a path from the root node to a leaf node. The value of a branch is calculated by appending the values of each node lying in the path (from root to leaf).
For example, if the nodes 1, 2, and 3 have values 1,0 and 2 respectively, then, the path 1→2→3
has a value 102, while the path 2→1→3 has the value 012 or 12 (leading zeroes are insignificant).
Find the sum of the values of all the branches in the tree. Since the answer can be huge, print it modulo 1e9 + 7.
Solution Approach :- We can use a Depth-First Search (DFS) traversal to calculate the sum of values of all branches in the binary tree. It can maintain a running total (cur) for each path and updates it while traversing the tree.
Algorithm :-
- The dfs function takes the adjacency list (g), visited array (vis), node values array (a), current node (node), and the current sum (cur).
- It marks the current node as visited and updates the current sum by appending the value of the current node.
- It then recursively traverses the unvisited children of the current node.
- If the current node is a leaf (no unvisited children), it updates the total sum (ans) by adding the current sum.
- The modulo operation is applied to both the current sum and the total sum at each step as per the modular arithmetic.
Time Complexity :- The time complexity of this solution is O(N), where N is the number of nodes in the binary tree. Each node is visited once during the DFS traversal.
Space Complexity :- The space complexity is O(N) due to the space used by the adjacency list, visited array, and node values array. The depth of the recursion call stack is also O(N) in the worst case.