algoadvance

Leetcode 129. Sum Root to Leaf Numbers

Problem Statement

The problem “Sum Root to Leaf Numbers” is defined as follows:

Given a binary tree where each node contains a single digit (0-9), each root-to-leaf path could represent a number. An example of this would be from the root to the leaf being 1→2→3, which represents the number 123. The goal is to find the total sum of all the numbers represented by the different root-to-leaf paths in the tree.

Clarifying Questions

1. Are there any constraints on the size of the tree?
   • Usually, the problem constraints for LeetCode problems are within reasonable input sizes for the problem to be solved efficiently, typically up to a few thousand nodes.
2. Are all nodes guaranteed to have value digits between 0 and 9?
   • Yes, each node in the binary tree contains a single digit, and valid input must be in the range 0-9.
3. What is the output if the tree is empty?
   • If the tree is empty, the sum should be 0.

Strategy

To solve this problem, we can use Depth-First Search (DFS) to traverse the tree. During the traversal:

• At each node, we maintain the current number formed.
• When reaching a leaf node (both left and right children are null), we add the current number to the total sum.

Steps

1. Start traversing from the root with an initial number of 0.
2. For each node, update the current number by: current_number = current_number * 10 + node->val.
3. If a leaf node is reached (both children null), add the current_number to the total sum.
4. Recursively traverse left and right subtrees with the updated number.
5. Return the total sum.

Code

Here’s how we can implement this in C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
    
private:
    int dfs(TreeNode* node, int currentSum) {
        if (!node) return 0;

        currentSum = currentSum * 10 + node->val;
        
        // If it's a leaf node, return the current sum.
        if (!node->left && !node->right) {
            return currentSum;
        }
        
        // Otherwise, proceed to the left and right children.
        int leftSum = dfs(node->left, currentSum);
        int rightSum = dfs(node->right, currentSum);
        
        return leftSum + rightSum;
    }
};

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the tree.
  • This is because each node is visited exactly once.
• Space Complexity: O(h), where h is the height of the tree.
  • In the worst case, the recursion stack will go as deep as the height of the tree. For a balanced tree, this will be O(log n), and for a skewed tree, this will be O(n).

This ensures an efficient traversal and summation of all root-to-leaf numbers in the tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?