Java Program For Sum Root to Leaf Numbers
Sum Root to Leaf Numbers is a popular interview problem which is asked in companies like Google & Microsoft. You can find this question in LeetCode & InterviewBit.
We have been given a binary tree where each node can contain any number between 0-9.
2 / \ 4 8
For the above tree, there are two root to leaf paths, 2->4 = 24 & 2->8 = 28. So result should be 24 + 28 = 52. In InterviewBit problem, we need to get the remainder after dividing the result by 1003 (result % 1003) to restrict number overflow. Number overflow can happen if tree has a lot of depth.
Below you can find the working Java solution for this problem. It will do a pre-order traversal & do a backtracking to find all possible solutions & add them to result. Time complexity is O(n) as we need to traverse the full tree once. Space complexity is constant O(1) if we don't consider recursion stack.