algoadvance

Leetcode 129. Sum Root to Leaf Numbers

Problem Statement:

Given a binary tree containing digits from 0-9 only, where each root-to-leaf path could represent a number, return the total sum of all root-to-leaf numbers.

A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf paths are 1->2 and 1->3.
1->2 represents the number 12.
1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Clarifying Questions:

1. Q: Are negative numbers involved in the tree nodes? A: No, the tree contains digits from 0-9 only.

2. Q: Is it possible for the tree to be empty? A: Yes, if the tree is empty then the sum should be 0.

3. Q: Should we consider the tree nodes as integers? A: Yes, each node in the tree is a digit from 0-9.

Strategy:

1. Tree Traversal: We will use Depth-First Search (DFS) to traverse the tree. DFS is suitable as we need to track each root-to-leaf path.

2. Carry Forward the Partial Number: As we go deeper into the tree, we will construct the number by carrying forward the partial number and multiplying it by 10 before adding the current node’s value.

3. Summing Up: When a leaf node is reached, the formed number is added to the sum.

4. Edge Case Handling: If the tree is empty, return 0.

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    
    private int dfs(TreeNode node, int currentSum) {
        if (node == null) {
            return 0;
        }
        
        currentSum = currentSum * 10 + node.val;
        
        // If it's a leaf node
        if (node.left == null && node.right == null) {
            return currentSum;
        }
        
        // DFS on left and right subtree
        int leftSum = dfs(node.left, currentSum);
        int rightSum = dfs(node.right, currentSum);
        
        return leftSum + rightSum;
    }
}

Time Complexity:

• Traversal Complexity: Each node is visited exactly once which makes the time complexity O(N), where N is the number of nodes in the tree.
• Space Complexity: In the worst case, the space complexity will be O(H) where H is the height of the tree. This is due to the recursion stack. In the case of a balanced tree, H = O(log N), and for a completely unbalanced tree, H = O(N).

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?