Similar Problems

Similar Problems not available

Sum Root To Leaf Numbers - Leetcode Solution


LeetCode:  Sum Root To Leaf Numbers Leetcode Solution

Difficulty: Medium

Topics: tree binary-tree depth-first-search  

The problem statement is:

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example 1:

Input: [1,2,3]

   / \
  2   3

Output: 25


The root-to-leaf path 1->2 represents the number 12.

The root-to-leaf path 1->3 represents the number 13.

Therefore, the sum is 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]

       / \
      9   0
     / \
    5   1

Output: 1026


The root-to-leaf path 4->9->5 represents the number 495.

The root-to-leaf path 4->9->1 represents the number 491.

The root-to-leaf path 4->0 represents the number 40.

Therefore, the sum is 495 + 491 + 40 = 1026.


The problem can be solved by traversing the tree in a depth-first manner. We can keep track of the current number formed by adding the current node’s value to the number so far. If the current node is a leaf, we can add the current number to the total sum. Otherwise, we can recursively traverse the node’s left and right children, passing the current number as an argument.


  • Initialize a global variable sum and set it to 0.
  • Define a helper function named dfs with parameters root and num.
  • If root is null, return.
  • If root is a leaf, add the current num to the sum by sum = sum + num*10 + root.val.
  • Recursively call the dfs function for the left and right children of root, passing num*10+root.val as the updated value of num.
  • Finally, call the dfs function for the root node with num = 0 to start the traversal from the root node.
  • Return the sum.


class Solution { int sum = 0; // global variable to store sum public int sumNumbers(TreeNode root) { dfs(root, 0); // calling helper function with root and initial num as 0 return sum; }

public void dfs(TreeNode root, int num){
    if(root == null){
    if(root.left==null && root.right==null){ // checking if node is leaf
        sum += (num*10) + root.val; // adding the current num to the sum
    dfs(root.left, num*10 + root.val); //recursive call for left child
    dfs(root.right, num*10 + root.val); //recursive call for right child


Time Complexity: The time complexity of the above algorithm is O(N), where N is the total number of nodes in the tree. This is because we are visiting each node once.

Space Complexity: The space complexity of the above algorithm is O(H), where H is the height of the tree. This is because the maximum number of recursive calls at any given time is equal to the height of the tree.

Sum Root To Leaf Numbers Solution Code