# Find the maximum sum from root to leaf path in Binary Tree

Here given code implementation process.

``````/*
C Program
Find the maximum sum from root to leaf path in Binary Tree
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

//Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//This is creating a binary tree node and return this
struct Node *get_node(int data)
{
// Create dynamic node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return new_node;
}
//Recursive function
//Display Inorder view of binary tree
void inorder(struct Node *node)
{
if (node)
{
inorder(node->left);
//Print node value
printf("  %d", node->data);
inorder(node->right);
}
}
//Find the maximum sum leaf to root path in a binary tree
void max_path__sum(struct Node *root, int *result, int sum)
{
if (root != NULL)
{
//Calculate path nodes sum of left subtree
max_path__sum(root->left, result, sum + root->data);
//Calculate path nodes sum of right subtree
max_path__sum(root->right, result, sum + root->data);
if (root->left == NULL && root->right == NULL)
{
//When a get leaf node
if ( *result < sum + root->data)
{
//When root to current leaf path sum is greater to previous result
//Get new result
*result = sum + root->data;
}
}
}
}
//This are handling the request to find max path sum
void path_sum(struct Node *root)
{
if (root == NULL)
{
printf("\nEmpty Binary Tree\n");
return;
}
//set initial result
int result = INT_MIN;
//Calculate max sum
max_path__sum(root, &result, 0);
printf("\n Binary Tree : ");
inorder(root);
//Display calculated result
printf("\n Maximum sum is  : %d\n", result);
}
int main()
{
struct Node *root = NULL;
/*
Construct Binary Tree
-----------------------

1
/    \
3      5
/ \    /  \
1   7  7    2
/    \
6      1
/
2
*/
root = get_node(1);
root->left = get_node(3);
root->left->left = get_node(1);
root->left->right = get_node(7);
root->left->right->left = get_node(6);
root->right = get_node(5);
root->right->right = get_node(2);
root->right->left = get_node(7);
root->right->left->right = get_node(1);
root->right->left->right->left = get_node(2);
path_sum(root);
return 0;
}``````

#### Output

`````` Binary Tree :   1  3  6  7  1  7  2  1  5  2
Maximum sum is  : 17``````
``````/*
Java Program
Find the maximum sum  from root to leaf path in Binary Tree
*/
//Node of Binary Tree
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
//Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
public Node root;
public int result;
public BinaryTree()
{
//Set initial tree root to null
this.root = null;
this.result = 0;
}
//Display Inorder view of binary tree
public void inorder(Node node)
{
if (node != null)
{
// Executing left subtree
inorder(node.left);
// Print node value
System.out.print("  " + node.data);
// Executing right subtree
inorder(node.right);
}
}
//Find the maximum sum leaf to root path in a binary tree
public void max_path__sum(Node root, int sum)
{
if (root != null)
{
//Calculate path nodes sum of left subtree
max_path__sum(root.left, sum + root.data);
//Calculate path nodes sum of right subtree
max_path__sum(root.right, sum + root.data);
if (root.left == null && root.right == null)
{
//When a get leaf node
if (this.result < sum + root.data)
{
//When root to current leaf path sum is greater to previous result
//Get new result
this.result = sum + root.data;
}
}
}
}
//This are handling the request to find max path sum
public void path_sum()
{
if (this.root == null)
{
System.out.print("\nEmpty Binary Tree\n");
return;
}
//Set initial result
this.result = Integer.MIN_VALUE;
//Calculate max sum
max_path__sum(this.root, 0);
System.out.print("\n Binary Tree : ");
inorder(this.root);
//Display calculated result
System.out.print("\n Maximum sum is  : " + this.result);
}
public static void main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------

1
/    \
3      5
/ \    /  \
1   7  7    2
/    \
6      1
/
2
*/
obj.root = new Node(1);
obj.root.left = new Node(3);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(7);
obj.root.left.right.left = new Node(6);
obj.root.right = new Node(5);
obj.root.right.right = new Node(2);
obj.root.right.left = new Node(7);
obj.root.right.left.right = new Node(1);
obj.root.right.left.right.left = new Node(2);
obj.path_sum();
}
}``````

#### Output

`````` Binary Tree :   1  3  6  7  1  7  2  1  5  2
Maximum sum is  : 17``````
``````//Include header file
#include <iostream>
#include<limits.h>
using namespace std;

/*
C++ Program
Find the maximum sum from root to leaf path in Binary Tree
*/

//Node of Binary Tree
class Node
{
public:
int data;
Node *left;
Node *right;
Node(int data)
{
//Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public:
Node *root;
int result;
BinaryTree()
{
//Set initial tree root to null
this->root = NULL;
this->result = 0;
}
//Display Inorder view of binary tree
void inorder(Node *node)
{
if (node != NULL)
{
// Executing left subtree
this->inorder(node->left);
// Print node value
cout << "  " << node->data;
// Executing right subtree
this->inorder(node->right);
}
}
//Find the maximum sum leaf to root path in a binary tree
void max_path__sum(Node *root, int sum)
{
if (root != NULL)
{
//Calculate path nodes sum of left subtree
this->max_path__sum(root->left, sum + root->data);
//Calculate path nodes sum of right subtree
this->max_path__sum(root->right, sum + root->data);
if (root->left == NULL && root->right == NULL)
{
//When a get leaf node
if (this->result < sum + root->data)
{
//When root to current leaf path sum is greater to previous result
//Get new result
this->result = sum + root->data;
}
}
}
}
//This are handling the request to find max path sum
void path_sum()
{
if (this->root == NULL)
{
cout << "\nEmpty Binary Tree\n";
return;
}
//Set initial result
this->result = INT_MIN;
//Calculate max sum
this->max_path__sum(this->root, 0);
cout << "\n Binary Tree : ";
this->inorder(this->root);
//Display calculated result
cout << "\n Maximum sum is  : " << this->result;
}
};
int main()
{
//Make object of Binary Tree
BinaryTree obj = BinaryTree();
/*
Construct Binary Tree
-----------------------

1
/    \
3      5
/ \    /  \
1   7  7    2
/    \
6      1
/
2
*/
obj.root = new Node(1);
obj.root->left = new Node(3);
obj.root->left->left = new Node(1);
obj.root->left->right = new Node(7);
obj.root->left->right->left = new Node(6);
obj.root->right = new Node(5);
obj.root->right->right = new Node(2);
obj.root->right->left = new Node(7);
obj.root->right->left->right = new Node(1);
obj.root->right->left->right->left = new Node(2);
obj.path_sum();
return 0;
}``````

#### Output

`````` Binary Tree :   1  3  6  7  1  7  2  1  5  2
Maximum sum is  : 17``````
``````//Include namespace system
using System;

/*
C# Program
Find the maximum sum from root to leaf path in Binary Tree
*/

//Node of Binary Tree
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
//Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
public Node root;
public int result;
public BinaryTree()
{
//Set initial tree root to null
this.root = null;
this.result = 0;
}
//Display Inorder view of binary tree
public void inorder(Node node)
{
if (node != null)
{
// Executing left subtree
inorder(node.left);
// Print node value
Console.Write("  " + node.data);
// Executing right subtree
inorder(node.right);
}
}
//Find the maximum sum leaf to root path in a binary tree
public void max_path__sum(Node root, int sum)
{
if (root != null)
{
//Calculate path nodes sum of left subtree
max_path__sum(root.left, sum + root.data);
//Calculate path nodes sum of right subtree
max_path__sum(root.right, sum + root.data);
if (root.left == null && root.right == null)
{
//When a get leaf node
if (this.result < sum + root.data)
{
//When root to current leaf path sum is greater to previous result
//Get new result
this.result = sum + root.data;
}
}
}
}
//This are handling the request to find max path sum
public void path_sum()
{
if (this.root == null)
{
Console.Write("\nEmpty Binary Tree\n");
return;
}
//Set initial result
this.result = int.MinValue;
//Calculate max sum
max_path__sum(this.root, 0);
Console.Write("\n Binary Tree : ");
inorder(this.root);
//Display calculated result
Console.Write("\n Maximum sum is  : " + this.result);
}
public static void Main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------

1
/    \
3      5
/ \    /  \
1   7  7    2
/    \
6      1
/
2
*/
obj.root = new Node(1);
obj.root.left = new Node(3);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(7);
obj.root.left.right.left = new Node(6);
obj.root.right = new Node(5);
obj.root.right.right = new Node(2);
obj.root.right.left = new Node(7);
obj.root.right.left.right = new Node(1);
obj.root.right.left.right.left = new Node(2);
obj.path_sum();
}
}``````

#### Output

`````` Binary Tree :   1  3  6  7  1  7  2  1  5  2
Maximum sum is  : 17``````
``````<?php
/*
Php Program
Find the maximum sum from root to leaf path in Binary Tree
*/

//Node of Binary Tree
class Node
{
public \$data;
public \$left;
public \$right;

function __construct(\$data)
{
//Set node value
\$this->data = \$data;
\$this->left = null;
\$this->right = null;
}
}
class BinaryTree
{
public \$root;
public \$result;

function __construct()
{
//Set initial tree root to null
\$this->root = null;
\$this->result = 0;
}
//Display Inorder view of binary tree
public	function inorder(\$node)
{
if (\$node != null)
{
// Executing left subtree
\$this->inorder(\$node->left);
// Print node value
echo "  ". \$node->data;
// Executing right subtree
\$this->inorder(\$node->right);
}
}
//Find the maximum sum leaf to root path in a binary tree
public	function max_path__sum(\$root, \$sum)
{
if (\$root != null)
{
//Calculate path nodes sum of left subtree
\$this->max_path__sum(\$root->left, \$sum + \$root->data);
//Calculate path nodes sum of right subtree
\$this->max_path__sum(\$root->right, \$sum + \$root->data);
if (\$root->left == null && \$root->right == null)
{
//When a get leaf node
if (\$this->result < \$sum + \$root->data)
{
//When root to current leaf path sum is greater to previous result
//Get new result
\$this->result = \$sum + \$root->data;
}
}
}
}
//This are handling the request to find max path sum
public	function path_sum()
{
if (\$this->root == null)
{
echo "\nEmpty Binary Tree\n";
return;
}
//Set initial result
\$this->result = -PHP_INT_MAX;
//Calculate max sum
\$this->max_path__sum(\$this->root, 0);
echo "\n Binary Tree : ";
\$this->inorder(\$this->root);
//Display calculated result
echo "\n Maximum sum is  : ". \$this->result;
}
}

function main()
{
//Make object of Binary Tree
\$obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------

1
/    \
3      5
/ \    /  \
1   7  7    2
/    \
6      1
/
2
*/
\$obj->root = new Node(1);
\$obj->root->left = new Node(3);
\$obj->root->left->left = new Node(1);
\$obj->root->left->right = new Node(7);
\$obj->root->left->right->left = new Node(6);
\$obj->root->right = new Node(5);
\$obj->root->right->right = new Node(2);
\$obj->root->right->left = new Node(7);
\$obj->root->right->left->right = new Node(1);
\$obj->root->right->left->right->left = new Node(2);
\$obj->path_sum();
}
main();``````

#### Output

`````` Binary Tree :   1  3  6  7  1  7  2  1  5  2
Maximum sum is  : 17``````
``````/*
Node Js Program
Find the maximum sum from root to leaf path in Binary Tree
*/

//Node of Binary Tree
class Node
{
constructor(data)
{
//Set node value
this.data = data;
this.left = null;
this.right = null;
}
}

class BinaryTree
{
constructor()
{
//Set initial tree root to null
this.root = null;
this.result = 0;
}
//Display Inorder view of binary tree
inorder(node)
{
if (node != null)
{
// Executing left subtree
this.inorder(node.left);
// Print node value
process.stdout.write("  " + node.data);
// Executing right subtree
this.inorder(node.right);
}
}
//Find the maximum sum leaf to root path in a binary tree
max_path__sum(root, sum)
{
if (root != null)
{
//Calculate path nodes sum of left subtree
this.max_path__sum(root.left, sum + root.data);
//Calculate path nodes sum of right subtree
this.max_path__sum(root.right, sum + root.data);
if (root.left == null && root.right == null)
{
//When a get leaf node
if (this.result < sum + root.data)
{
//When root to current leaf path sum is greater to previous result
//Get new result
this.result = sum + root.data;
}
}
}
}
//This are handling the request to find max path sum
path_sum()
{
if (this.root == null)
{
process.stdout.write("\nEmpty Binary Tree\n");
return;
}
//Set initial result
this.result = -Number.MAX_VALUE;
//Calculate max sum
this.max_path__sum(this.root, 0);
process.stdout.write("\n Binary Tree : ");
this.inorder(this.root);
//Display calculated result
process.stdout.write("\n Maximum sum is  : " + this.result);
}
}

function main()
{
//Make object of Binary Tree
var obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------

1
/    \
3      5
/ \    /  \
1   7  7    2
/    \
6      1
/
2
*/
obj.root = new Node(1);
obj.root.left = new Node(3);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(7);
obj.root.left.right.left = new Node(6);
obj.root.right = new Node(5);
obj.root.right.right = new Node(2);
obj.root.right.left = new Node(7);
obj.root.right.left.right = new Node(1);
obj.root.right.left.right.left = new Node(2);
obj.path_sum();
}
main();``````

#### Output

`````` Binary Tree :   1  3  6  7  1  7  2  1  5  2
Maximum sum is  : 17``````
``````import sys

#   Python 3 Program
#   Find the maximum sum from root to leaf path in Binary Tree

# Node of Binary Tree
class Node :

def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None

class BinaryTree :

def __init__(self) :
# Set initial tree root to null
self.root = None
self.result = 0

# Display Inorder view of binary tree
def inorder(self, node) :
if (node != None) :
#  Executing left subtree
self.inorder(node.left)
#  Print node value
print("  ", node.data, end = "")
#  Executing right subtree
self.inorder(node.right)

# Find the maximum sum leaf to root path in a binary tree
def max_path__sum(self, root, sum) :
if (root != None) :
# Calculate path nodes sum of left subtree
self.max_path__sum(root.left, sum + root.data)
# Calculate path nodes sum of right subtree
self.max_path__sum(root.right, sum + root.data)
if (root.left == None and root.right == None) :
# When a get leaf node
if (self.result < sum + root.data) :
# When root to current leaf path sum is greater to previous result
# Get new result
self.result = sum + root.data

# This are handling the request to find max path sum
def path_sum(self) :
if (self.root == None) :
print("\nEmpty Binary Tree\n", end = "")
return

# Set initial result
self.result = -sys.maxsize
# Calculate max sum
self.max_path__sum(self.root, 0)
print("\n Binary Tree : ", end = "")
self.inorder(self.root)
# Display calculated result
print("\n Maximum sum is  : ", self.result, end = "")

def main() :
# Make object of Binary Tree
obj = BinaryTree()
#
# 		Construct Binary Tree
# 		-----------------------
# 		      1
# 		   /    \
# 		  3      5
# 		 / \    /  \
# 		1   7  7    2
# 		   /    \
# 		  6      1
# 		        /
# 		       2
#

obj.root = Node(1)
obj.root.left = Node(3)
obj.root.left.left = Node(1)
obj.root.left.right = Node(7)
obj.root.left.right.left = Node(6)
obj.root.right = Node(5)
obj.root.right.right = Node(2)
obj.root.right.left = Node(7)
obj.root.right.left.right = Node(1)
obj.root.right.left.right.left = Node(2)
obj.path_sum()

if __name__ == "__main__": main()``````

#### Output

`````` Binary Tree :    1   3   6   7   1   7   2   1   5   2
Maximum sum is  :  17``````
``````#   Ruby Program
#   Find the maximum sum from root to leaf path in Binary Tree

# Node of Binary Tree
class Node

# Define the accessor and reader of class Node
attr_accessor :data, :left, :right

def initialize(data)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
class BinaryTree

# Define the accessor and reader of class BinaryTree
attr_accessor :root, :result

def initialize()
# Set initial tree root to null
self.root = nil
self.result = 0
end
# Display Inorder view of binary tree
def inorder(node)

if (node != nil)

#  Executing left subtree
self.inorder(node.left)
#  Print node value
print("  ", node.data)
#  Executing right subtree
self.inorder(node.right)
end
end
# Find the maximum sum leaf to root path in a binary tree
def max_path__sum(root, sum)

if (root != nil)
# Calculate path nodes sum of left subtree
self.max_path__sum(root.left, sum + root.data)
# Calculate path nodes sum of right subtree
self.max_path__sum(root.right, sum + root.data)
if (root.left == nil && root.right == nil)

# When a get leaf node
if (self.result < sum + root.data)

# When root to current leaf path sum is greater to previous result
# Get new result
self.result = sum + root.data
end
end
end
end
# This are handling the request to find max path sum
def path_sum()

if (self.root == nil)
print("\nEmpty Binary Tree\n")
return
end
# Set initial result
self.result = -(2 ** (0. size * 8 - 2))
# Calculate max sum
self.max_path__sum(self.root, 0)
print("\n Binary Tree : ")
self.inorder(self.root)
# Display calculated result
print("\n Maximum sum is  : ", self.result)
end
end
def main()

# Make object of Binary Tree
obj = BinaryTree.new()
#
# 		Construct Binary Tree
# 		-----------------------
# 		      1
# 		   /    \
# 		  3      5
# 		 / \    /  \
# 		1   7  7    2
# 		   /    \
# 		  6      1
# 		        /
# 		       2
#

obj.root = Node.new(1)
obj.root.left = Node.new(3)
obj.root.left.left = Node.new(1)
obj.root.left.right = Node.new(7)
obj.root.left.right.left = Node.new(6)
obj.root.right = Node.new(5)
obj.root.right.right = Node.new(2)
obj.root.right.left = Node.new(7)
obj.root.right.left.right = Node.new(1)
obj.root.right.left.right.left = Node.new(2)
obj.path_sum()
end
main()``````

#### Output

`````` Binary Tree :   1  3  6  7  1  7  2  1  5  2
Maximum sum is  : 17``````
``````/*
Scala Program
Find the maximum sum from root to leaf path in Binary Tree
*/
//Node of Binary Tree
class Node(var data: Int,
var left: Node,
var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: Node,
var result: Int)
{
def this()
{
this(null, 0);
}
//Display Inorder view of binary tree
def inorder(node: Node): Unit = {
if (node != null)
{
// Executing left subtree
inorder(node.left);
// Print node value
print("  " + node.data);
// Executing right subtree
inorder(node.right);
}
}
//Find the maximum sum leaf to root path in a binary tree
def max_path__sum(root: Node, sum: Int): Unit = {
if (root != null)
{
//Calculate path nodes sum of left subtree
max_path__sum(root.left, sum + root.data);
//Calculate path nodes sum of right subtree
max_path__sum(root.right, sum + root.data);
if (root.left == null && root.right == null)
{
//When a get leaf node
if (this.result < sum + root.data)
{
//When root to current leaf path sum is greater to previous result
//Get new result
this.result = sum + root.data;
}
}
}
}
//This are handling the request to find max path sum
def path_sum(): Unit = {
if (this.root == null)
{
print("\nEmpty Binary Tree\n");
return;
}
//Set initial result
this.result = Int.MinValue;
//Calculate max sum
max_path__sum(this.root, 0);
print("\n Binary Tree : ");
inorder(this.root);
//Display calculated result
print("\n Maximum sum is  : " + this.result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object of Binary Tree
var obj: BinaryTree = new BinaryTree();
/*
Construct Binary Tree
-----------------------

1
/    \
3      5
/ \    /  \
1   7  7    2
/    \
6      1
/
2
*/
obj.root = new Node(1);
obj.root.left = new Node(3);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(7);
obj.root.left.right.left = new Node(6);
obj.root.right = new Node(5);
obj.root.right.right = new Node(2);
obj.root.right.left = new Node(7);
obj.root.right.left.right = new Node(1);
obj.root.right.left.right.left = new Node(2);
obj.path_sum();
}
}``````

#### Output

`````` Binary Tree :   1  3  6  7  1  7  2  1  5  2
Maximum sum is  : 17``````
``````/*
Swift 4 Program
Find the maximum sum from root to leaf path in Binary Tree
*/

//Node of Binary Tree
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
//Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}

class BinaryTree
{
var root: Node? ;
var result: Int;
init()
{
//Set initial tree root to null
self.root = nil;
self.result = 0;
}
//Display Inorder view of binary tree
func inorder(_ node: Node? )
{
if (node != nil)
{
// Executing left subtree
self.inorder(node!.left);
// Print node value
print("  ", node!.data, terminator: "");
// Executing right subtree
self.inorder(node!.right);
}
}
//Find the maximum sum leaf to root path in a binary tree
func max_path__sum(_ root: Node? , _ sum : Int)
{
if (root != nil)
{
//Calculate path nodes sum of left subtree
self.max_path__sum(root!.left, sum + root!.data);
//Calculate path nodes sum of right subtree
self.max_path__sum(root!.right, sum + root!.data);
if (root!.left == nil && root!.right == nil)
{
//When a get leaf node
if (self.result < sum + root!.data)
{
//When root to current leaf path sum is greater to previous result
//Get new result
self.result = sum + root!.data;
}
}
}
}
//This are handling the request to find max path sum
func path_sum()
{
if (self.root == nil)
{
print("\nEmpty Binary Tree\n", terminator: "");
return;
}
//Set initial result
self.result = Int.min;
//Calculate max sum
self.max_path__sum(self.root, 0);
print("\n Binary Tree : ", terminator: "");
self.inorder(self.root);
//Display calculated result
print("\n Maximum sum is  : ", self.result, terminator: "");
}
}
func main()
{
//Make object of Binary Tree
let obj: BinaryTree = BinaryTree();
/*
Construct Binary Tree
-----------------------

1
/    \
3      5
/ \    /  \
1   7  7    2
/    \
6      1
/
2
*/
obj.root = Node(1);
obj.root!.left = Node(3);
obj.root!.left!.left = Node(1);
obj.root!.left!.right = Node(7);
obj.root!.left!.right!.left = Node(6);
obj.root!.right = Node(5);
obj.root!.right!.right = Node(2);
obj.root!.right!.left = Node(7);
obj.root!.right!.left!.right = Node(1);
obj.root!.right!.left!.right!.left = Node(2);
obj.path_sum();
}
main();``````

#### Output

`````` Binary Tree :    1   3   6   7   1   7   2   1   5   2
Maximum sum is  :  17``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.