Approach

To solve this problem, we can use a Depth-First Search (DFS) strategy to traverse the tree from the root to each leaf node. The main idea is to accumulate the value of the path from root to leaf as we traverse down the tree.

  1. DFS Traversal: Start from the root node and recursively explore the left and right subtrees.

  2. Accumulate the Current Path Value: Maintain a currentSum variable that accumulates the number formed by concatenating node values. For each node, the new value is calculated as:

currentSum = currentSum * 10 + node.val

This way, you effectively build the number from the root to the current node.

  1. Base Case (Leaf Node): When you reach a leaf node (a node with no left or right children), return the currentSum as this is the number formed by the path from root to that leaf.

  2. Recursive Calls for Left and Right Subtrees: If a node has left or right children, recursively calculate the sum for both subtrees and return the sum of the results.

  3. Sum All Numbers: The final result will be the sum of all the numbers formed by the paths from the root to all leaf nodes.

Code Implementation 

var sumNumbers = function (root) {
    const helper = (node, currentSum) => {
        if (node == null) return 0;

        currentSum = currentSum * 10 + node.val;

        // If it's a leaf node, return the current sum
        if (node.left === null && node.right === null) {
            return currentSum;
        }

        // Recurse for left and right subtrees
        return helper(node.left, currentSum) + helper(node.right, currentSum);
    };

    return helper(root, 0);
};

Time and Space Complexity Analysis

Time Complexity: O(n)

  • Every node in the binary tree is visited exactly once.
  • Since there are n nodes in the tree, the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity: O(h)

  • The space complexity is determined by the maximum depth of the recursion stack, which corresponds to the height of the tree (h).
  • In the worst case, where the tree is skewed (i.e., a linked list), the height is n, leading to a space complexity of O(n).
  • In the best case, where the tree is balanced, the height is logarithmic (i.e., O(log n)), so the space complexity is O(log n).

Conclusion

This problem can be efficiently solved using a recursive depth-first traversal, where we accumulate the number formed along each path from the root to the leaf nodes. By leveraging recursion, we can handle binary trees of varying structures, including skewed and balanced trees. The time complexity is linear, making the solution both efficient and easy to implement.