LeetCode 129: Sum Root to Leaf Numbers Solution

Master LeetCode problem 129 (Sum Root to Leaf Numbers), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

129. Sum Root to Leaf Numbers

Medium

Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To solve this problem, we can perform a Depth First Search (DFS) traversal of the binary tree. At each node, we calculate the sum of the numbers formed so far by traversing from the root to that node. We recursively traverse the left and right child nodes while updating the sum. When we reach a leaf node, we add the final number formed to the total sum.

Time Complexity:
The time complexity of this approach is O(n), where n is the number of nodes in the binary tree.

Space Complexity:
The space complexity is O(h), where h is the height of the binary tree.

Solution Code

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    
    private int dfs(TreeNode node, int currSum) {
        if (node == null) {
            return 0;
        }
        
        currSum = currSum * 10 + node.val;
        
        if (node.left == null && node.right == null) {
            return currSum;
        }
        
        int leftSum = dfs(node.left, currSum);
        int rightSum = dfs(node.right, currSum);
        
        return leftSum + rightSum;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 129 (Sum Root to Leaf Numbers)?

This page provides optimized solutions for LeetCode problem 129 (Sum Root to Leaf Numbers) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 129 (Sum Root to Leaf Numbers)?

The time complexity for LeetCode 129 (Sum Root to Leaf Numbers) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 129 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 129 in Java, C++, or Python.

Back to LeetCode Solutions