In this problem, we need to find the sum of all binary numbers that are formed by traversing each root to leaf path in the tree. Please refer below link to read the full problem statement.
In this problem, we will do a preorder traversal and keep track of the current sum from the root till the current node in a variable called curr .
At a particular node, the value of the current sum will be 2*currSum+node.val. When we reach any of the leaf nodes, we return te current sum value i.e curr, because we have completed a valid root to leaf path and we need a return and add this value to the overall result.
If the current node is not a leaf node, we add the values returned from calling this sum on both left and right subtrees.
Below is the accepted solution.
The time complexity of this solution will be O(N) since we are doing a preOrder traversal. In this case, we will visit a node at max 3 times, one while calling the method on the root and 2 visits when returning from the root’s left and right recursion calls. So overall time complexity will be linear only.
Space complexity will be O(h) for the recursion calls.
