Sponsored
Sponsored
This approach involves using a recursive function to traverse the binary tree from the root to the leaves. During the traversal, we calculate the binary number formed by the path from the root to the current node, then sum up the numbers obtained when a leaf node is reached. The traversal is achieved using depth-first search (DFS).
Time Complexity: O(n), where n is the number of nodes in the tree because each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack. In the worst case, it could be O(n).
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public int sumRootToLeaf(TreeNode root) {
10 return calculateSum(root, 0);
11 }
12
13 private int calculateSum(TreeNode node, int currentSum) {
14 if (node == null) {
15 return 0;
16 }
17 currentSum = (currentSum << 1) | node.val;
18 if (node.left == null && node.right == null) {
19 return currentSum;
20 }
21 return calculateSum(node.left, currentSum) + calculateSum(node.right, currentSum);
22 }
23}In this Java solution, the `calculateSum` method is used to execute a recursive DFS through the binary tree. When a leaf node is encountered, the computed binary to decimal conversion is returned, else we continue traversing the tree.
This approach utilizes an iterative technique employing a stack to carry out a DFS. In each iteration, nodes are retrieved alongside their corresponding computed binary sum. This method is advantageous when stack overflow due to recursion is a concern, as it emulates recursion iteratively.
Time Complexity: O(n), due to visiting each node once.
Space Complexity: O(n), bounded by the stack's requirement to store node-state pairs.
1function TreeNode(val, left, right
This JavaScript solution uses a stack to carry out an iterative DFS, forming binary numbers for root-to-leaf paths and calculating their sum without recursion. Each stack entry comprises a node and its ongoing binary sum, unraveling all paths systematically.