Sum of all the numbers that are formed from root to leaf paths

Last Updated : 21 Sep, 2023

Given a binary tree, where every node value is a Digit from 1-9. Find the sum of all the numbers which are formed from root to leaf paths.
For example, consider the following Binary Tree.

           6
       /      \
     3          5
   /   \          \
  2     5          4  
      /   \
     7     4
  There are 4 leaves, hence 4 root to leaf paths:
   Path                    Number
  6->3->2                   632
  6->3->5->7               6357
  6->3->5->4               6354
  6->5>4                    654   
Answer = 632 + 6357 + 6354 + 654 = 13997

The idea is to do a preorder traversal of the tree. In the preorder traversal, keep track of the value calculated till the current node, let this value be val. For every node, we update the val as val*10 plus the node’s data.

Implementation:

C++

// C++ program to find sum of
// all paths from root to leaves 
#include <bits/stdc++.h>
using namespace std;
 
class node 
{ 
    public:
    int data; 
    node *left, *right; 
}; 
 
// function to allocate new node with given data 
node* newNode(int data) 
{ 
    node* Node = new node();
    Node->data = data; 
    Node->left = Node->right = NULL; 
    return (Node); 
} 
 
// Returns sum of all root to leaf paths.
// The first parameter is root 
// of current subtree, the second 
// parameter is value of the number formed 
// by nodes from root to this node 
int treePathsSumUtil(node *root, int val) 
{ 
    // Base case 
    if (root == NULL) return 0; 
 
    // Update val 
    val = (val*10 + root->data); 
 
    // if current node is leaf, return the current value of val 
    if (root->left==NULL && root->right==NULL) 
    return val; 
 
    // recur sum of values for left and right subtree 
    return treePathsSumUtil(root->left, val) + 
        treePathsSumUtil(root->right, val); 
} 
 
// A wrapper function over treePathsSumUtil() 
int treePathsSum(node *root) 
{ 
    // Pass the initial value as 0
    // as there is nothing above root 
    return treePathsSumUtil(root, 0); 
} 
 
// Driver code
int main() 
{ 
    node *root = newNode(6); 
    root->left = newNode(3); 
    root->right = newNode(5); 
    root->left->left = newNode(2); 
    root->left->right = newNode(5); 
    root->right->right = newNode(4); 
    root->left->right->left = newNode(7); 
    root->left->right->right = newNode(4); 
    cout<<"Sum of all paths is "<<treePathsSum(root); 
    return 0; 
} 
 
// This code is contributed by rathbhupendra

C

// C program to find sum of all paths from root to leaves
#include <stdio.h>
#include <stdlib.h>
 
struct node
{
    int data;
    struct node *left, *right;
};
 
// function to allocate new node with given data
struct node* newNode(int data)
{
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
 
// Returns sum of all root to leaf paths. The first parameter is root
// of current subtree, the second parameter is value of the number formed
// by nodes from root to this node
int treePathsSumUtil(struct node *root, int val)
{
    // Base case
    if (root == NULL)  return 0;
 
    // Update val
    val = (val*10 + root->data);
 
    // if current node is leaf, return the current value of val
    if (root->left==NULL && root->right==NULL)
       return val;
 
    // recur sum of values for left and right subtree
    return treePathsSumUtil(root->left, val) +
           treePathsSumUtil(root->right, val);
}
 
// A wrapper function over treePathsSumUtil()
int treePathsSum(struct node *root)
{
    // Pass the initial value as 0 as there is nothing above root
    return treePathsSumUtil(root, 0);
}
 
// Driver function to test the above functions
int main()
{
    struct node *root = newNode(6);
    root->left        = newNode(3);
    root->right       = newNode(5);
    root->left->left  = newNode(2);
    root->left->right = newNode(5);
    root->right->right = newNode(4);
    root->left->right->left = newNode(7);
    root->left->right->right = newNode(4);
    printf("Sum of all paths is %d", treePathsSum(root));
    return 0;
}

Java

// Java program to find sum of all numbers that are formed from root
// to leaf paths
  
// A binary tree node
class Node 
{
    int data;
    Node left, right;
      
    Node(int item) 
    {
        data = item;
        left = right = null;
    }
}
  
class BinaryTree 
{
    Node root;
  
    // Returns sum of all root to leaf paths. The first parameter is 
    // root of current subtree, the second parameter is value of the  
    // number formed by nodes from root to this node
    int treePathsSumUtil(Node node, int val) 
    {
        // Base case
        if (node == null)
            return 0;
  
        // Update val
        val = (val * 10 + node.data);
  
        // if current node is leaf, return the current value of val
        if (node.left == null && node.right == null)
            return val;
  
        // recur sum of values for left and right subtree
        return treePathsSumUtil(node.left, val)
                + treePathsSumUtil(node.right, val);
    }
  
    // A wrapper function over treePathsSumUtil()
    int treePathsSum(Node node) 
    {
        // Pass the initial value as 0 as there is nothing above root
        return treePathsSumUtil(node, 0);
    }
  
    // Driver program to test above functions
    public static void main(String args[]) 
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(6);
        tree.root.left = new Node(3);
        tree.root.right = new Node(5);
        tree.root.right.right = new Node(4);
        tree.root.left.left = new Node(2);
        tree.root.left.right = new Node(5);
        tree.root.left.right.right = new Node(4);
        tree.root.left.right.left = new Node(7);
          
        System.out.print("Sum of all paths is " + 
                                 tree.treePathsSum(tree.root));   
    }    
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Python program to find sum of all paths from root to leaves
 
# A Binary tree node
class Node:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Returns sums of all root to leaf paths. The first parameter is root
# of current subtree, the second paramete"r is value of the number
# formed by nodes from root to this node
def treePathsSumUtil(root, val):
 
    # Base Case
    if root is None:
        return 0
 
    # Update val
    val = (val*10 + root.data)
 
    # If current node is leaf, return the current value of val
    if root.left is None and root.right is None:
        return val
 
    # Recur sum of values for left and right subtree
    return (treePathsSumUtil(root.left, val) +
            treePathsSumUtil(root.right, val))
 
# A wrapper function over treePathSumUtil()
def treePathsSum(root):
     
    # Pass the initial value as 0 as there is nothing above root
    return treePathsSumUtil(root, 0)
 
# Driver function to test above function
root = Node(6)
root.left = Node(3)
root.right = Node(5)
root.left.left = Node(2)
root.left.right = Node(5)
root.right.right = Node(4)
root.left.right.left = Node(7)
root.left.right.right = Node(4)
print ("Sum of all paths is", treePathsSum(root))
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// c# program to find sum of all numbers 
// that are formed from root to leaf paths 
using System;
 
// A binary tree node 
public class Node
{
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class GFG
{
public Node root;
 
// Returns sum of all root to leaf paths. 
// The first parameter is root of current 
// subtree, the second parameter is value 
// of the number formed by nodes from root
// to this node 
public virtual int treePathsSumUtil(Node node,
                                    int val)
{
    // Base case 
    if (node == null)
    {
        return 0;
    }
 
    // Update val 
    val = (val * 10 + node.data);
 
    // if current node is leaf, return 
    // the current value of val 
    if (node.left == null && node.right == null)
    {
        return val;
    }
 
    // recur sum of values for left and right subtree 
    return treePathsSumUtil(node.left, val) +
           treePathsSumUtil(node.right, val);
}
 
// A wrapper function over treePathsSumUtil() 
public virtual int treePathsSum(Node node)
{
    // Pass the initial value as 0 as 
    // there is nothing above root 
    return treePathsSumUtil(node, 0);
}
 
// Driver Code
public static void Main(string[] args)
{
    GFG tree = new GFG();
    tree.root = new Node(6);
    tree.root.left = new Node(3);
    tree.root.right = new Node(5);
    tree.root.right.right = new Node(4);
    tree.root.left.left = new Node(2);
    tree.root.left.right = new Node(5);
    tree.root.left.right.right = new Node(4);
    tree.root.left.right.left = new Node(7);
 
    Console.Write("Sum of all paths is " + 
                   tree.treePathsSum(tree.root));
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
// JavaScript program to find sum of
// all paths from root to leaves
class node
{
     
    constructor(data){
        this.data = data;
        this.left = this.right = null;
    }
 
}
 
// Returns sum of all root to leaf paths.
// The first parameter is root
// of current subtree, the second
// parameter is value of the number formed
// by nodes from root to this node
function treePathsSumUtil(root,val)
{
    // Base case
    if (root == null) return 0;
 
    // Update val
    val = (val*10 + root.data);
 
    // if current node is leaf, return the current value of val
    if (root.left==null && root.right==null)
      return val;
 
    // recur sum of values for left and right subtree
    return treePathsSumUtil(root.left, val) + treePathsSumUtil(root.right, val);
}
 
// A wrapper function over treePathsSumUtil()
function treePathsSum(root)
{
    // Pass the initial value as 0
    // as there is nothing above root
    return treePathsSumUtil(root, 0);
}
 
// Driver code
 
let root = new node(6);
root.left = new node(3);
root.right = new node(5);
root.left.left = new node(2);
root.left.right = new node(5);
root.right.right = new node(4);
root.left.right.left = new node(7);
root.left.right.right = new node(4);
document.write("Sum of all paths is "+treePathsSum(root));
 
// This code is contributed by shinjanpatra
</script>

Output

Sum of all paths is 13997

Time Complexity: The above code is a simple preorder traversal code that visits every node exactly once. Therefore, the time complexity is O(n) where n is the number of nodes in the given binary tree.
Auxiliary Space: O(n)

Another Approach: We can also solve this problem by first finding all the paths from the root to the leaf . Then we convert all paths into numbers. In the end, we will add those numbers.

Implementation:

C++

// C++ program to find sum of all paths from root to leaves
 
// A Binary tree node
#include <bits/stdc++.h>
using namespace std;
 
// A Binary tree node
class Node 
{ 
    public:
    int data; 
    Node *left, *right; 
   
    // Constructor to create a new node
      Node(int val)
    {
      data = val;
      left = right = NULL; 
    }
}; 
 
void treePathsSumUtil(Node* root, vector<string> currPath, 
                      vector<vector<string>> &allPath)
{
    // Base Case
    if (root == NULL)
        return;
 
    // append the root data in string format in currPath
    currPath.push_back((to_string)(root->data));
 
    // if we found a leaf node we copy the currPath to allPath
    if (root->left == NULL && root->right == NULL)
        allPath.push_back(currPath);
 
    // traverse in the left subtree
    treePathsSumUtil(root->left, currPath, allPath);
 
    // traverse in the right subtree
    treePathsSumUtil(root->right, currPath, allPath);
 
    // remove the current element from the path
    currPath.pop_back();
}
int treePathsSum(Node* root)
{
   
    // store all the root to leaf path in allPath
    vector<vector<string>> allPath;
    vector<string> v;
    treePathsSumUtil(root, v, allPath);
   
    // store the sum
    int s = 0;
 
    for(auto pathNumber : allPath)
    {
        string k="";
       
        // join the pathNumbers to convert them  
      // into the number to calculate sum
        for(auto x: pathNumber)
            k = k+x;
        s += stoi(k);
    }
    return s;
}
  
// Driver code
int main() 
{ 
    Node *root = new Node(6); 
    root->left = new Node(3); 
    root->right = new Node(5); 
    root->left->left = new Node(2); 
    root->left->right = new Node(5); 
    root->right->right = new Node(4); 
    root->left->right->left = new Node(7); 
    root->left->right->right = new Node(4); 
    cout<<"Sum of all paths is "<<treePathsSum(root); 
    return 0; 
} 
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Java

// Java program to find sum of all paths from root to leaves
import java.util.*;
 
public class GFG {
 
  // A Binary tree node
  static class Node {
    int data;
    Node left, right;
 
    // Constructor to create a new node
    Node(int val)
    {
      data = val;
      left = right = null;
    }
  };
 
  static void
    treePathsSumUtil(Node root, ArrayList<String> currPath,
                     ArrayList<ArrayList<String> > allPath)
  {
    // Base Case
    if (root == null)
      return;
 
    // append the root data in string format in currPath
    currPath.add(("" + root.data));
 
    // if we found a leaf node we copy the currPath to
    // allPath
    if (root.left == null && root.right == null)
      allPath.add(new ArrayList<>(currPath));
 
    // traverse in the left subtree
    treePathsSumUtil(root.left, currPath, allPath);
 
    // traverse in the right subtree
    treePathsSumUtil(root.right, currPath, allPath);
 
    // remove the current element from the path
    currPath.remove(currPath.size() - 1);
  }
  static int treePathsSum(Node root)
  {
 
    // store all the root to leaf path in allPath
    ArrayList<ArrayList<String> > allPath
      = new ArrayList<>();
    ArrayList<String> v = new ArrayList<>();
    treePathsSumUtil(root, v, allPath);
 
    // store the sum
    int s = 0;
 
    for (ArrayList<String> pathNumber : allPath) {
      String k = "";
 
      // join the pathNumbers to convert them
      // into the number to calculate sum
      for (String x : pathNumber)
        k += x;
      s += Integer.parseInt(k);
    }
    return s;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    Node root = new Node(6);
    root.left = new Node(3);
    root.right = new Node(5);
    root.left.left = new Node(2);
    root.left.right = new Node(5);
    root.right.right = new Node(4);
    root.left.right.left = new Node(7);
    root.left.right.right = new Node(4);
    System.out.println("Sum of all paths is "
                       + treePathsSum(root));
  }
}
 
// This code is contributed by Karandeep1234

Python3

# Python program to find sum of all paths from root to leaves
 
# A Binary tree node
 
 
class Node:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
def treePathsSumUtil(root, currPath, allPath):
   
    # Base Case
    if root is None:
        return
 
    # append the root data in string format in currPath
    currPath.append(str(root.data))
 
    # if we found a leaf node we copy the currPath to allPath
    if root.left is None and root.right is None:
        allPath.append(currPath.copy())
 
    # traverse in the left subtree
    treePathsSumUtil(root.left, currPath, allPath)
 
    # traverse in the right subtree
    treePathsSumUtil(root.right, currPath, allPath)
 
    # remove the current element from the path
    del currPath[-1]
 
 
def treePathsSum(root):
    # store all the root to leaf path in allPath
    allPath = []
 
    treePathsSumUtil(root, [], allPath)
    # store the sum
    s = 0
 
    for pathNumber in allPath:
        # join the pathNumbers to convert them  into the number to calculate sum
        k = "".join(pathNumber)
        s += int(k)
    return s
 
 
# Driver function to test above function
root = Node(6)
root.left = Node(3)
root.right = Node(5)
root.left.left = Node(2)
root.left.right = Node(5)
root.right.right = Node(4)
root.left.right.left = Node(7)
root.left.right.right = Node(4)
print("Sum of all paths is", treePathsSum(root))
 
# this code is contributed by Vivek Maddeshiya

C#

//C# code for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
    // A Binary tree node
    class Node
    {
        public int data;
        public Node left, right;
 
        // Constructor to create a new node
        public Node(int val)
        {
            data = val;
            left = right = null;
        }
    }
    static void treePathsSumUtil(Node root, List<string> currPath, List<List<string>> allPath)
    {
        // Base Case
        if (root == null)
            return;
 
        // append the root data in string format in currPath
        currPath.Add(root.data.ToString());
 
        // if we found a leaf node we copy the currPath to
        // allPath
        if (root.left == null && root.right == null)
            allPath.Add(new List<string>(currPath));
 
        // traverse in the left subtree
        treePathsSumUtil(root.left, currPath, allPath);
 
        // traverse in the right subtree
        treePathsSumUtil(root.right, currPath, allPath);
 
        // remove the current element from the path
        currPath.RemoveAt(currPath.Count - 1);
    }
 
    static int treePathsSum(Node root)
    {
 
        // store all the root to leaf path in allPath
        List<List<string>> allPath = new List<List<string>>();
        List<string> v = new List<string>();
        treePathsSumUtil(root, v, allPath);
 
        // store the sum
        int s = 0;
 
        foreach (List<string> pathNumber in allPath)
        {
            string k = "";
 
            // join the pathNumbers to convert them
            // into the number to calculate sum
            foreach (string x in pathNumber)
                k += x;
            s += int.Parse(k);
        }
        return s;
    }
 
    // Driver code
    static void Main(string[] args)
    {
        Node root = new Node(6);
        root.left = new Node(3);
        root.right = new Node(5);
        root.left.left = new Node(2);
        root.left.right = new Node(5);
        root.right.right = new Node(4);
        root.left.right.left = new Node(7);
        root.left.right.right = new Node(4);
        Console.WriteLine("Sum of all paths is " + treePathsSum(root));
    }
}

Javascript

// JavaScript program to find sum of all paths from root to leaves
 
// A Binary tree node
class Node {
    // Constructor to create a new node
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
function treePathsSumUtil(root, currPath, allPath) {
    // Base Case
    if (root === null) {
        return;
    }
 
    // append the root data in string format in currPath
    currPath.push(String(root.data));
 
    // if we found a leaf node we copy the currPath to allPath
    if (root.left === null && root.right === null) {
        allPath.push(currPath.slice());
    }
 
    // traverse in the left subtree
    treePathsSumUtil(root.left, currPath, allPath);
 
    // traverse in the right subtree
    treePathsSumUtil(root.right, currPath, allPath);
 
    // remove the current element from the path
    currPath.pop();
}
 
function treePathsSum(root) {
    // store all the root to leaf path in allPath
    let allPath = [];
 
    treePathsSumUtil(root, [], allPath);
    // store the sum
    let s = 0;
 
    for (const pathNumber of allPath) {
        // join the pathNumbers to convert them into the number to calculate sum
        let k = pathNumber.join("");
        s += Number(k);
    }
    return s;
}
 
// Driver function to test above function
let root = new Node(6);
root.left = new Node(3);
root.right = new Node(5);
root.left.left = new Node(2);
root.left.right = new Node(5);
root.right.right = new Node(4);
root.left.right.left = new Node(7);
root.left.right.right = new Node(4);
console.log("Sum of all paths is", treePathsSum(root));
 
// This code is contributed by adityamaharshi21

Output

Sum of all paths is 13997

Time Complexity: Time Complexity of this approach will be O(n^2) because we are traversing the allPath and joining currPath to the allPath array .
Auxiliary Space: O(n)

Iterative Depth-First Search (DFS) using a Stack:

The basic idea behind the "Iterative Depth-First Search (DFS) using a Stack" approach is to traverse the binary tree iteratively in a depth-first manner while keeping track of the path sum from the root to the current node. We use a stack to store pairs of nodes and their corresponding path sums.

Follow the steps below to implement the above idea:

Start with an initial sum value of 0 and create an empty stack.
Push the root node onto the stack along with its value as the initial path sum.
While the stack is not empty, do the following:
a. Pop a node and its corresponding path sum from the stack.
b. If the popped node is a leaf (i.e., it has no left and right children), add the path sum to the overall result.
c. If the popped node has a right child, push the right child onto the stack with the updated path sum. The updated path sum is obtained by multiplying the current path sum by 10 and adding the value of the right child.
d. If the popped node has a left child, push the left child onto the stack with the updated path sum. The updated path sum is obtained by multiplying the current path sum by 10 and adding the value of the left child.
Once the stack is empty, return the overall result, which represents the sum of all the numbers formed from root to leaf paths.

Below is the implementation:

C++

// c++ code to implement the DFS approach
#include <iostream>
#include <stack>
using namespace std;
 
// Tree node structure
struct Node {
    int data;
    Node *left, *right;
};
 
long long treePathsSum(Node* root)
{
    // Base case: if the tree is empty, return 0
    if (root == nullptr)
        return 0;
 
    long long sum = 0;
    stack<pair<Node*, long long> > stk;
    stk.push(
        { root,
          root->data }); // Push the root node with its
                         // value as the initial path sum
 
    while (!stk.empty()) {
        Node* currNode = stk.top().first;
        long long currSum = stk.top().second;
        stk.pop();
 
        if (currNode->left == nullptr
            && currNode->right == nullptr) {
            // Reached a leaf node, add the path sum to the
            // overall result
            sum += currSum;
        }
        else {
            // If the current node has a right child, push
            // it onto the stack with the updated path sum
            if (currNode->right != nullptr) {
                stk.push({ currNode->right,
                           (currSum * 10)
                               + currNode->right->data });
            }
 
            // If the current node has a left child, push it
            // onto the stack with the updated path sum
            if (currNode->left != nullptr) {
                stk.push({ currNode->left,
                           (currSum * 10)
                               + currNode->left->data });
            }
        }
    }
 
    return sum;
}
 
// Driver code
int main()
{
    /*
                6
              /   \
             3     5
            / \     \
           2   5     4
               / \
              7   4
    */
    Node* root = new Node();
    root->data = 6;
    root->left = new Node();
    root->left->data = 3;
    root->left->left = new Node();
    root->left->left->data = 2;
    root->left->right = new Node();
    root->left->right->data = 5;
    root->left->right->left = new Node();
    root->left->right->left->data = 7;
    root->left->right->right = new Node();
    root->left->right->right->data = 4;
    root->right = new Node();
    root->right->data = 5;
    root->right->right = new Node();
    root->right->right->data = 4;
 
    long long result = treePathsSum(root);
    cout
        << "Sum of numbers formed from root to leaf paths: "
        << result << endl;
 
    return 0;
}
//This code is contributed by Veerendra_Singh_Rajpoot

Java

//java code to implement the DFS approach
import java.util.Stack;
import java.util.AbstractMap;
 
// Tree node structure
class Node {
    int data;
    Node left, right;
 
    Node(int item) {
        data = item;
        left = right = null;
    }
}
 
public class TreePathSum {
 // function to find paths sum using dfs 
    static long treePathsSum(Node root) {
        if (root == null)
            return 0;
 
        long sum = 0;
      //creating stack of pair
        Stack<AbstractMap.SimpleEntry<Node, Long>> stk = new Stack<>();
        stk.push(new AbstractMap.SimpleEntry<>(root, (long) root.data));
 
        while (!stk.isEmpty()) {
            Node currNode = stk.peek().getKey();
            long currSum = stk.peek().getValue();
            stk.pop();
 
            if (currNode.left == null && currNode.right == null) {
                sum += currSum;
            } else {
                if (currNode.right != null) {
                    stk.push(new AbstractMap.SimpleEntry<>(currNode.right, (currSum * 10) + currNode.right.data));
                }
                if (currNode.left != null) {
                    stk.push(new AbstractMap.SimpleEntry<>(currNode.left, (currSum * 10) + currNode.left.data));
                }
            }
        }
 
        return sum;
    }
    //Driver Code
    public static void main(String[] args) {
        /*
                    6
                  /   \
                 3     5
                / \     \
               2   5     4
                   / \
                  7   4
        */
        Node root = new Node(6);
        root.left = new Node(3);
        root.left.left = new Node(2);
        root.left.right = new Node(5);
        root.left.right.left = new Node(7);
        root.left.right.right = new Node(4);
        root.right = new Node(5);
        root.right.right = new Node(4);
 
        long result = treePathsSum(root);
        System.out.println("Sum of numbers formed from root to leaf paths: " + result);
    }
}
//This code is contributed by Veerendra_Singh_Rajpoot

Python3

# Tree node structure
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
def treePathsSum(root):
    # Base case: if the tree is empty, return 0
    if root is None:
        return 0
 
    sum = 0
    stk = []
    stk.append((root, root.data))  # Push the root node with its value as the initial path sum
 
    while stk:
        currNode, currSum = stk.pop()
 
        if currNode.left is None and currNode.right is None:
            # Reached a leaf node, add the path sum to the overall result
            sum += currSum
        else:
            # If the current node has a right child, push it onto the stack 
            # with the updated path sum
            if currNode.right:
                stk.append((currNode.right, (currSum * 10) + currNode.right.data))
 
            # If the current node has a left child, push it onto the stack with the 
            # updated path sum
            if currNode.left:
                stk.append((currNode.left, (currSum * 10) + currNode.left.data))
 
    return sum
 
# Driver code
"""
                6
              /   \
             3     5
            / \     \
           2   5     4
               / \
              7   4
"""
root = Node(6)
root.left = Node(3)
root.left.left = Node(2)
root.left.right = Node(5)
root.left.right.left = Node(7)
root.left.right.right = Node(4)
root.right = Node(5)
root.right.right = Node(4)
 
result = treePathsSum(root)
print("Sum of numbers formed from root to leaf paths:", result)
# THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002)

C#

// C# code to implement the DFS approach
using System;
using System.Collections.Generic;
 
// Tree node structure
class Node {
    public int data;
    public Node left, right;
}
 
public class GFG {
    static long TreePathsSum(Node root)
    {
        // Base case: if the tree is empty, return 0
        if (root == null)
            return 0;
 
        long sum = 0;
        Stack<Tuple<Node, long> > stack
            = new Stack<Tuple<Node, long> >();
        stack.Push(new Tuple<Node, long>(
            root,
            root.data)); // Push the root node with its
                         // value as the initial path sum
 
        while (stack.Count > 0) {
            Node currNode = stack.Peek().Item1;
            long currSum = stack.Peek().Item2;
            stack.Pop();
 
            if (currNode.left == null
                && currNode.right == null) {
                // Reached a leaf node, add the path sum to
                // the overall result
                sum += currSum;
            }
            else {
                // If the current node has a right child,
                // push it onto the stack with the updated
                // path sum
                if (currNode.right != null) {
                    stack.Push(new Tuple<Node, long>(
                        currNode.right,
                        (currSum * 10)
                            + currNode.right.data));
                }
 
                // If the current node has a left child,
                // push it onto the stack with the updated
                // path sum
                if (currNode.left != null) {
                    stack.Push(new Tuple<Node, long>(
                        currNode.left,
                        (currSum * 10)
                            + currNode.left.data));
                }
            }
        }
 
        return sum;
    }
 
    // Driver code
    static void Main()
    {
        /*
                    6
                  /   \
                 3     5
                / \     \
               2   5     4
                   / \
                  7   4
        */
        Node root = new Node();
        root.data = 6;
        root.left = new Node();
        root.left.data = 3;
        root.left.left = new Node();
        root.left.left.data = 2;
        root.left.right = new Node();
        root.left.right.data = 5;
        root.left.right.left = new Node();
        root.left.right.left.data = 7;
        root.left.right.right = new Node();
        root.left.right.right.data = 4;
        root.right = new Node();
        root.right.data = 5;
        root.right.right = new Node();
        root.right.right.data = 4;
 
        long result = TreePathsSum(root);
        Console.WriteLine(
            "Sum of numbers formed from root to leaf paths: "
            + result);
    }
}
 
// This code is contributed by Susobhan Akhuli

Javascript

// Tree node structure
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
function treePathsSum(root) {
    // Base case: if the tree is empty, return 0
    if (root === null)
        return 0;
 
    let sum = 0;
    let stk = [];
    stk.push([root, root.data]); // Push the root node with its value as the initial path sum
 
    while (stk.length > 0) {
        let [currNode, currSum] = stk.pop();
 
        if (currNode.left === null && currNode.right === null) {
            // Reached a leaf node, add the path sum to the overall result
            sum += currSum;
        }
        else {
            // If the current node has a right child, push it onto the stack with the updated path sum
            if (currNode.right !== null) {
                stk.push([currNode.right, (currSum * 10) + currNode.right.data]);
            }
 
            // If the current node has a left child, push it onto the stack with the updated path sum
            if (currNode.left !== null) {
                stk.push([currNode.left, (currSum * 10) + currNode.left.data]);
            }
        }
    }
 
    return sum;
}
 
// Driver code
/*
                6
              /   \
             3     5
            / \     \
           2   5     4
               / \
              7   4
*/
let root = new Node(6);
root.left = new Node(3);
root.left.left = new Node(2);
root.left.right = new Node(5);
root.left.right.left = new Node(7);
root.left.right.right = new Node(4);
root.right = new Node(5);
root.right.right = new Node(4);
 
let result = treePathsSum(root);
console.log("Sum of numbers formed from root to leaf paths: " + result);
// THIS CODE IS CONTRIBUTED BY CHANDAN AGARWAL

Output

Sum of numbers formed from root to leaf paths: 13997

Time Complexity: O(N), where N is the number of nodes in the binary tree. In the worst case, we need to visit each node once.

Auxiliary Space: O(H), where H is the height of the binary tree. In the worst case, the height of the binary tree can be equal to the number of nodes (N), resulting in a space complexity of O(N). This space is used to store the stack during the iterative DFS traversal.

GeeksforGeeks

Improve

Previous Article

Sum of nodes at k-th level in a tree represented as string

Merge Two Binary Trees by doing Node Sum (Recursive and Iterative)

Similar Reads

Remove nodes from Binary Tree such that sum of all remaining root-to-leaf paths is atleast K

Given a Binary Tree and an integer K, the task is to delete nodes from the given Tree such that the sum of all nodes of all remaining root to leaf paths is at least K. Examples: Input: K = 27 Output: 5 4 8 5 6 11Explanation:Below are the paths whose sum is less than 27: 5 -> 3 -> 9: Path Sum = 5 + 3 + 9 = 17.5 -> 4 -> 9: Path Sum = 5 +

Print all the paths from root to leaf, with a specified sum in Binary tree

Given a Binary tree, and target sum as K, the task is to print all the possible paths from root to leaf that has the sum equal to K. Examples: Input: K = 22 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 Output: [5, 4, 11, 2] [5, 8, 4 , 5] Explanation: In the above tree, the paths [5, 4, 11, 2] and [5, 8, 4, 5] are the paths from root to a leaf which has

Given a binary tree, print out all of its root-to-leaf paths one per line.

Given the roots of a tree. print out all of its root-to-leaf paths one per line.. Algorithm: initialize: pathlen = 0, path[1000] /*1000 is some max limit for paths, it can change*/ /*printPathsRecur traverses nodes of tree in preorder */ printPathsRecur(tree, path[], pathlen) 1) If node is not NULL then a) push data to path array: path[pathlen] = n

Print all the root-to-leaf paths of a Binary Tree whose XOR is non-zero

Given a Binary Tree, the task is to print all root-to-leaf paths of this tree whose xor value is non-zero. Examples: Input: 10 / \ 10 3 / \ 10 3 / \ / \ 7 3 42 13 / 7 Output: 10 3 10 7 10 3 3 42 Explanation: All the paths in the given binary tree are : {10, 10} xor value of the path is = 10 ^ 10 = 0 {10, 3, 10, 7} xor value of the path is = 10 ^ 3

Print all root-to-leaf paths with maximum count of even nodes

Given a Binary tree, the task is to print all possible root-to-leaf paths having a maximum number of even valued nodes. Examples: Input: 2 / \ 6 3 / \ \ 4 7 11 / \ \ 10 12 1 Output: 2 -> 6 -> 4 -> 10 2 -> 6 -> 4 -> 12 Explanation: Count of even nodes on the path 2 -> 6 -> 4 -> 10 = 4 Count of even nodes on the path 2 -

Print all root to leaf paths of an N-ary tree

Given an N-Ary tree, the task is to print all root to leaf paths of the given N-ary Tree. Examples: Input: 1 / \ 2 3 / / \ 4 5 6 / \ 7 8 Output:1 2 41 3 51 3 6 71 3 6 8 Input: 1 / | \ 2 5 3 / \ \ 4 5 6Output:1 2 41 2 51 51 3 6 Approach: The idea to solve this problem is to start traversing the N-ary tree using depth-first search and keep inserting

Given a binary tree, print all root-to-leaf paths

For the below example tree, all root-to-leaf paths are: 10 –> 8 –> 3 10 –> 8 –> 5 10 –> 2 –> 2 Recommended PracticeRoot to Leaf PathsTry It! Algorithm: Use a path array path[] to store current root to leaf path. Traverse from root to all leaves in top-down fashion. While traversing, store data of all nodes in current path in array

Print all root to leaf paths with there relative positions

Given a binary tree, print the root to the leaf path, but add "_" to indicate the relative position. Example: Input : Root of below tree A / \ B C / \ / \ D E F G Output : All root to leaf paths _ _ A _ B D _ A B _ E A _ C F A _ C _ _ G Asked In: Google Interview The idea base on print path in vertical order. Below is complete algorithm : We do Pre

Find if there is a pair in root to a leaf path with sum equals to root's data

Given a binary tree, find if there is a pair in root to a leaf path such that sum of values in pair is equal to root's data. For example, in below tree there are no pairs in any root to leaf path with sum equal to root's data. The idea is based on hashing and tree traversal. The idea is similar to method 2 of array pair sum problem. Create an empty

Sum of Bitwise AND of the sum of all leaf and non-leaf nodes for each level of a Binary Tree

Given a Binary Tree consisting of N nodes, the task is to find the sum of Bitwise AND of the sum of all leaf nodes and the sum of all non-leaf nodes for each level in the given Tree. Examples: Input: Below is the given tree: 5 / \ 3 9 / \ 6 4 \ 7Output: 5Explanation: For Level 1: leaf node sum = 0, non-leaf node sum = 5. So, 0&5 = 0. For Level

Article Tags :

Practice Tags :