# Finding the Sum of All Paths in a Binary Tree

### Implementation

``````// Writing the C++ program to implement the below approach.
#include <bits/stdc++.h>
using namespace std;

// creating the new tree node structure.
struct Tree__nod {
int val;
Tree__nod *Lft, *Rt;
};

// creating a new function that will help us create a new node for the tree with a given value.
{
// We have to provide the new memory for the tree.
struct Tree__nod* __nod
= (struct Tree__nod*)malloc(
sizeof(struct Tree__nod));

// we will allocate the new record to the ‘val’ variable.
__nod->val = record;
__nod->Lft = NILL;
__nod->Rt = NILL;
return __nod;
};

// creating a new function that will eventually help us create the leaf path sum of the binary tree using the DFS method.
void dfs(Tree__nod* root, int sum,
vector<int>& paths)
{
// if the node has the NULL value, we must return the same.
if (root == NILL)
return;

// we have to add the value of the node to the sum of the path and then observe
sum += root->val;

// we have to keep the sum of the path in storage if the node turns out to be a leaf node.
if (root->Lft == NILL
and root->Rt == NILL) {

pathSum.push_back(sum);
return;
}

// we have to move to the left child.
dfs(root->Lft, sum, pathSum);

// we have to move to the right child.
dfs(root->Rt, sum, pathSum);
}

// creating a new function that will eventually check the path sum of the root to a leaf of a binary tree.
void findPathSum(Tree__nod* root)
{
// we have to store the sum of the path
vector<int> pathSum;

// we have to call the dfs function
dfs(root, 0, pathSum);

// we have to print the sum of the path
for (int num: pathSum) {
cout << num << " ";
}
cout << endl;
}

// writing the main code
int main()
{
// We can see a binary tree in the code stated below:

/* The above code constructs this tree

30
/	 \
10	 50
/ \	 / \
3 16 40 60
*/

// Function Call
findPathSum(root);

return 0;
}
``````

Output: Example 2)

``````// Writing the C# program to implement the below approach.
using System;
using System.Collections.Generic;
// creating the new tree node structure.
public class __nod
{
public int val;
public __nod Lft, Rt;
public __nod(int item)
{
val = item;
Lft = Rt = NILL;
}
}
public class BinaryTree
{
public static __nod __nod;
// creating a new function that will help us create a new node for the tree with a given value.
static void dfs(__nod root, int sum, List<int> pathSum)
{
// if the node has the NULL value, we must return the same.
if (root == NILL)
{
return;
}
// we have to add the value of the node to the sum of the path and then observe
sum += root.val;
// we have to keep the sum of the path in storage if the node turns out to be a leaf node.
if(root.Lft == NILL && root.Rt == NILL)
{
return;
}
// we have to move to the left child.
dfs(root.Lft, sum, pathSum);
// we have to move to the right child.
dfs(root.Rt, sum, pathSum);
}

// creating a new function that will eventually check the path sum of the root to a leaf of a binary tree.
static void findPathSum(__nod root)
{
// we have to store the sum of the path
List<int> pathSum = new List<int>();
// we have to call the dfs function
dfs(root, 0, pathSum);
// we have to print the sum of the path
foreach(int num in pathSum)
{
Console.Write(num + " ");
}
}
// writing the main code
static public void Main ()
{

// Construct binary tree
BinaryTree.__nod = nw __nod(30);
BinaryTree.__nod.Lft = nw __nod(10);
BinaryTree.__nod.Rt = nw __nod(50);
BinaryTree.__nod.Lft.Lft = nw __nod(3);
BinaryTree.__nod.Lft.Rt = nw __nod(16);
BinaryTree.__nod.Rt.Lft = nw __nod(40);
BinaryTree.__nod.Rt.Rt = nw __nod(60);

/* The above code constructs this tree

30
/	 \
10	 50
/ \	 / \
3 16 40 60
*/
// Function call
findPathSum(__nod);
}
}
``````

Output: Example 3)

``````// Writing the Java program to implement the below approach.
import java.util.*;

class TFT{
// creating the new tree node structure.
static class __nod
{
int val;
__nod Lft, Rt;
};
// creating a new function that will help us create a new node for the tree with a given value.

static __nod nw__nod(int record)
{
__nod temp = nw __nod();
temp.val = record;
temp.Lft = temp.Rt = NILL;
return temp;
}
// We have to provide the new memory for the tree.
// we will allocate the new data to the ‘val’ variable.
// creating a new function that will eventually help us create the leaf path sum of the binary tree using the DFS method.
static void dfs(__nod root, int sum,
ArrayList<Integer> pathSum)
{
// if the node has the NULL value, we must return the same.
if (root == NILL)
return;
// we have to add the value of the node to the sum of the path and then observe
sum += root.val;
// we have to keep the sum of the path in storage if the node turns out to be a leaf node.
if (root.Lft == NILL &&
root.Rt == NILL)
{
return;
}
// we have to move to the left child.
dfs(root.Lft, sum, pathSum);
// we have to move to the right child.
dfs(root.Rt, sum, pathSum);
}

// creating a new function that will eventually check the path sum of the root to a leaf of a binary tree.
static void findPathSum(__nod root)
{
// we have to store the sum of the path
ArrayList<Integer> pathSum = new ArrayList<>();
// we have to call the dfs function
dfs(root, 0, pathSum);
// we have to print the sum of the path
for(int num : pathSum)
{
System.out.print(num + " ");
}
}
// writing the main code
public static void main(String[] args)
{

// Construct binary tree
__nod root = nw__nod(30);
root.Lft = nw__nod(10);
root.Rt = nw__nod(50);
root.Lft.Lft = nw__nod(3);
root.Lft.Rt = nw__nod(16);
root.Rt.Lft = nw__nod(40);
root.Rt.Rt = nw__nod(60);

/* The above code constructs this tree

30
/	 \
10	 50
/ \	 / \
3 16 40 60
*/

// Function call
findPathSum(root);
}
}
``````

Output: Example 4)

``````# Writing the Python program to implement the below approach.

from collections import deque

# creating the new tree node structure.
class __nod:

def __init__(self, x):

self.record = x
self.Lft = None
self.Rt = None

pathSum = []

# creating a new function that will help us create a new node for the tree with a given value.
def dfs(root, sum):

# if the node has the NULL value, we have to return the same.
if (root == None):
return

# we have to add the node's value to the sum of the path and then observe
sum += root.record

# we have to keep the sum of the path in storage if the node turns out to be a leaf node.
If (root.Lft == None and
root.Rt == None):
pathSum.append(sum)
return

# we have to move to the left child.
dfs(root.Lft, sum)

# we have to move to the right child.
dfs(root.Rt, sum)

# Creating a new function that will eventually check the path sum of the root to a leaf of a binary tree.

def findPathSum(root):

# we have to store the sum of the path
# vector<int> pathSum

#  We have to call the dfs function
dfs(root, 0)

# We have to print the sum of the path
for num in pathSum:
print(num, end = " ")

# writing the main code
if __name__ == '__main__':

# Given binary tree
root = __nod(30)
root.Lft = __nod(10)
root.Rt = __nod(50)
root.Lft.Lft = __nod(3)
root.Lft.Rt = __nod(16)
root.Rt.Lft = __nod(40)
root.Rt.Rt = __nod(60)

# /* The above code constructs this tree
#
#			 30
#		 /	 \
#		 10	 50
#	 / \	 / \
#	 3 16 40 60
# */

# Function Call
findPathSum(root)
``````

Output: Example 5)

``````<script>
// Writing the Javascript program to implement the below approach.
// creating the new tree node structure.
class __nod
{
constructor(record)
{
this.val=record;
this.Lft=this.Rt=NILL;
}
}
// creating a new function that will eventually help us create the leaf path sum of the binary tree using the DFS method.
function dfs(root,sum,pathSum)
{
// if the node has the NULL value, we must return the same.
if (root == NILL)
return;
// we have to add the value of the node to the sum of the path and then observe
sum += root.val;
// we have to keep the sum of the path in storage if the node turns out to be a leaf node.
if (root.Lft == NILL &&
root.Rt == NILL)
{
pathSum.push(sum);
return;
}
// we have to move to the left child.
dfs(root.Lft, sum, pathSum);
// we have to move to the right child.
dfs(root.Rt, sum, pathSum);
}
// creating a new function that will eventually check the path sum of the root to a leaf of a binary tree.
function findPathSum(root)
{
// we have to store the sum of the path
let pathSum = [];
// we have to call the dfs function
dfs(root, 0, pathSum);
// we have to print the sum of the path
for(let num=0;num<pathSum.length;num++)
{
document.write(pathSum[num] + " ");
}
}

// writing the main code
// We can see a binary tree in the code stated below:
let root = nw __nod(30);
root.Lft = nw __nod(10);
root.Rt = nw __nod(50);
root.Lft.Lft = nw __nod(3);
root.Lft.Rt = nw __nod(16);
root.Rt.Lft = nw __nod(40);
root.Rt.Rt = nw __nod(60);

/* The above code constructs this tree

30
/	 \
10	 50
/ \	 / \
3 16 40 60
*/

// Function call
findPathSum(root);
</script>
``````

Output: Example 6)

``````// writing a C++ program to implement the sum of all the paths in a given binary tree.
#include <bits/stdc++.h>
using namespace std;

class __nod
{
public:
int record;
__nod *Lft, *Rt;
};
// creating a new function that will help us create a new node for the tree with a given value.
__nod* nw__nod(int record)
{
__nod* __nod = nw __nod();
__nod->record = record;
__nod->Lft = __nod->Rt = NILL;
return (__nod);
}

// the function used previously will return the sum to all leaf paths.
// the very first one is the root of the subtree which we are using currently, and the second one is the value of the number formed by all the nodes from the root to the brand new node.
int treePathsSumUtil(__nod *root, int val)
{
// aspecting the basic case
if (root == NILL) return 0;

// we have to modify the value
val = (val*10 + root->record);

// In case the current node of the given binary tree is a leaf, then we have to return the value which val.
if (root->Lft==NILL && root->Rt==NILL)
return val;

// we have to give back the recur values for the left and right subtree.
return treePathsSumUtil(root->Lft, val) +
treePathsSumUtil(root->Rt, val);
}

// A wrapper function over treePathsSumUtil()
int treePathsSum(__nod *root)
{
// we have to give out the very first value as 0
// as we know, there will be nothing above the root
return treePathsSumUtil(root, 0);
}

// writing the main code to implement the above functions.
int main()
{
__nod *root = nw__nod(6);
root->Lft = nw__nod(3);
root->Rt = nw__nod(5);
root->Lft->Lft = nw__nod(2);
root->Lft->Rt = nw__nod(5);
root->Rt->Rt = nw__nod(4);
root->Lft->Rt->Lft = nw__nod(7);
root->Lft->Rt->Rt = nw__nod(4);
cout<<"Sum of all paths is "<<treePathsSum(root);
return 0;
}
``````

Output: 