Find the sum of longest path from root to leaf node

Given a binary tree, Our goal is to get the sum of longest path in this tree.

Example
/* Binary Tree
-----------------------
        1
     /    \
    2      5
   / \    /  \
  1   7  7    2
     /    \    \
    9      1   -3
          / 
        -7 
*/
/* First Path
-----------------------
      1
     / 
    2 
   /
  1 

    Length : 3
    Sum    : 4
*/

/* Second Path
-----------------------
      1
     /  
    2 
     \ 
      7
     / 
    9

    Length : 4
    Sum    : 19    
*/

/* Third Path
-----------------------
        1
         \
          5
         /  
        7  
         \  
          1 
         / 
       -7 

    Length : 5
    Sum    : 7  
*/


/* Fourth Path
-----------------------
        1
         \
          5
           \
            2
             \
             -3


    Length : 4
    Sum    : 5          
*/

Output :  7
[Because path 3 are length is higher to other]

If in case more than one path contains same resultant length then in this situation we accept sum of first (first path). Here given code implementation process.

/*
  C Program 
+ Find the sum of longest path from root to leaf node
*/
#include <stdio.h>

#include <stdlib.h>
 //structure of Binary Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
//Create a binary tree nodes and node fields (data,pointer) 
//And returning the reference of newly nodes
struct Node *insert(int data)
{
	//create dynamic memory to new binary tree 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; //Initially node left-pointer is NULL
		new_node->right = NULL; //Initially node right-pointer is NULL
	}
	else
	{
		printf("Memory Overflow\n");
		exit(0); //Terminate program execution
	}
	//return reference
	return new_node;
}
//Calculate sum of longest path in given binary tree
void long_path_result(struct Node *root, int *height, int *result, int sum, int level)
{
	if (root != NULL)
	{
		//Recursively calculating the value of height and sum of path
		long_path_result(root->left, height, result, sum + root->data, level + 1);
		long_path_result(root->right, height, result, sum + root->data, level + 1);
		//Check current root node is leaf or not
		if (root->left == NULL && root->right == NULL)
		{
			//Check previous calculate height is small or not
			if ( *height < level)
			{
				//When gets a new long height
				*height = level;
              	*result = sum + root->data;
			}
			else if ( *height == level && *result < sum + root->data)
			{
				//When Two depth are same and new result are larger
				*result = sum + root->data;
			}
		}
	}
}
//function which is handling the request of calculating longest path sum
void longest_path_sum(struct Node *root)
{
	int result = 0, height = 0;
	long_path_result(root, &height, &result, 0, 0);
	//Display result
	printf("Result : %d\n", result);
}
int main()
{
	struct Node *root = NULL;
	/* Construct Binary Tree
	-----------------------
	        1
	     /    \
	    2      5
	   / \    /  \
	  1   7  7    2
	     /    \    \
	    9      1   -3
	          / 
	        -7 
	*/
	//Insertion of binary tree nodes
	root = insert(1);
	root->left = insert(2);
	root->left->left = insert(1);
	root->left->right = insert(7);
	root->left->right->left = insert(9);
	root->right = insert(5);
	root->right->right = insert(2);
	root->right->left = insert(7);
	root->right->left->right = insert(1);
	root->right->left->right->left = insert(-7);
	root->right->right->right = insert(-3);
	longest_path_sum(root);
	return 0;
}

Output

Result : 7
/* 
  Java Program 
  Find the sum of longest path from root to leaf node
 */

//Binary Tree node
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 height;
	public int result;
	public BinaryTree()
	{
		//set initial tree root to null
		this.root = null;
		this.height = 0;
		this.result = 0;
	}
	//Calculate sum of longest path in given binary tree
	public void long_path_result(Node root, int sum, int level)
	{
		if (root != null)
		{
			//Recursively calculating the value of height and sum of path
			long_path_result(root.left, sum + root.data, level + 1);
			long_path_result(root.right, sum + root.data, level + 1);
			//Check current root node is leaf or not
			if (root.left == null && root.right == null)
			{
				//Check previous calculate height is small or not
				if (this.height < level)
				{
					//When gets a new long height
					this.height = level;
					this.result = sum + root.data;
				}
				else if (this.height == level && this.result < sum + root.data)
				{
					//When Two depth are same and new result are larger
					this.result = sum + root.data;
				}
			}
		}
	}
	//function which is handling the request of calculating longest path sum
	public void longest_path_sum()
	{
		//Set default value
		this.result = 0;
		this.height = 0;
		long_path_result(this.root, 0, 0);
		System.out.print("Result : " + this.result + "\n");
	}
	public static void main(String[] args)
	{
		//Make object of Binary Tree
		BinaryTree obj = new BinaryTree();
		/*  Construct Binary tree
		-----------------------

		            1
		         /    \
		        2      5
		       / \    /  \
		      1   7  7    2
		         /    \    \
		        9      1   -3
		              / 
		            -7 
		*/
		//Insertion of binary tree nodes
		obj.root = new Node(1);
		obj.root.left = new Node(2);
		obj.root.left.left = new Node(1);
		obj.root.left.right = new Node(7);
		obj.root.left.right.left = new Node(9);
		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(-7);
		obj.root.right.right.right = new Node(-3);
		obj.longest_path_sum();
	}
}

Output

Result : 7
//Include header file
#include <iostream>
using namespace std;

/*
  C++ Program 
  Find the sum of longest path from root to leaf node
 */

//Binary Tree node
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 height;
	int result;
	BinaryTree()
	{
		//set initial tree root to null
		this->root = NULL;
		this->height = 0;
		this->result = 0;
	}
	//Calculate sum of longest path in given binary tree
	void long_path_result(Node *root, int sum, int level)
	{
		if (root != NULL)
		{
			//Recursively calculating the value of height and sum of path
			this->long_path_result(root->left, sum + root->data, level + 1);
			this->long_path_result(root->right, sum + root->data, level + 1);
			//Check current root node is leaf or not
			if (root->left == NULL && root->right == NULL)
			{
				//Check previous calculate height is small or not
				if (this->height < level)
				{
					//When gets a new long height
					this->height = level;
					this->result = sum + root->data;
				}
				else if (this->height == level && this->result < sum + root->data)
				{
					//When Two depth are same and new result are larger
					this->result = sum + root->data;
				}
			}
		}
	}
	//function which is handling the request of calculating longest path sum
	void longest_path_sum()
	{
		//Set default value
		this->result = 0;
		this->height = 0;
		this->long_path_result(this->root, 0, 0);
		cout << "Result : " << this->result << "\n";
	}
};
int main()
{
	//Make object of Binary Tree
	BinaryTree obj = BinaryTree();
    /*  Construct Binary tree
    -----------------------

                1
             /    \
            2      5
           / \    /  \
          1   7  7    2
             /    \    \
            9      1   -3
                  / 
                -7 
    */
	//Insertion of binary tree nodes
	obj.root = new Node(1);
	obj.root->left = new Node(2);
	obj.root->left->left = new Node(1);
	obj.root->left->right = new Node(7);
	obj.root->left->right->left = new Node(9);
	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(-7);
	obj.root->right->right->right = new Node(-3);
	obj.longest_path_sum();
	return 0;
}

Output

Result : 7
//Include namespace system
using System;
/* 
  C# Program 
  Find the sum of longest path from root to leaf node
 */

//Binary Tree node
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 height;
	public int result;
	public BinaryTree()
	{
		//set initial tree root to null
		this.root = null;
		this.height = 0;
		this.result = 0;
	}
	//Calculate sum of longest path in given binary tree
	public void long_path_result(Node root, int sum, int level)
	{
		if (root != null)
		{
			//Recursively calculating the value of height and sum of path
			long_path_result(root.left, sum + root.data, level + 1);
			long_path_result(root.right, sum + root.data, level + 1);
			//Check current root node is leaf or not
			if (root.left == null && root.right == null)
			{
				//Check previous calculate height is small or not
				if (this.height < level)
				{
					//When gets a new long height
					this.height = level;
					this.result = sum + root.data;
				}
				else if (this.height == level && this.result < sum + root.data)
				{
					//When Two depth are same and new result are larger
					this.result = sum + root.data;
				}
			}
		}
	}
	//function which is handling the request of calculating longest path sum
	public void longest_path_sum()
	{
		//Set default value
		this.result = 0;
		this.height = 0;
		long_path_result(this.root, 0, 0);
		Console.Write("Result : " + this.result + "\n");
	}
	public static void Main(String[] args)
	{
		//Make object of Binary Tree
		BinaryTree obj = new BinaryTree();
		/*  Construct Binary tree
				-----------------------

				            1
				         /    \
				        2      5
				       / \    /  \
				      1   7  7    2
				         /    \    \
				        9      1   -3
				              / 
				            -7 
				*/
		//Insertion of binary tree nodes
		obj.root = new Node(1);
		obj.root.left = new Node(2);
		obj.root.left.left = new Node(1);
		obj.root.left.right = new Node(7);
		obj.root.left.right.left = new Node(9);
		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(-7);
		obj.root.right.right.right = new Node(-3);
		obj.longest_path_sum();
	}
}

Output

Result : 7
<?php
/* 
  Php Program 
  Find the sum of longest path from root to leaf node
 */

//Binary Tree node
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 $height;
	public $result;

	function __construct()
	{
		//set initial tree root to null
		$this->root = null;
		$this->height = 0;
		$this->result = 0;
	}
	//Calculate sum of longest path in given binary tree
	public	function long_path_result($root, $sum, $level)
	{
		if ($root != null)
		{
			//Recursively calculating the value of height and sum of path
			$this->long_path_result($root->left, $sum + $root->data, $level + 1);
			$this->long_path_result($root->right, $sum + $root->data, $level + 1);
			//Check current root node is leaf or not
			if ($root->left == null && $root->right == null)
			{
				//Check previous calculate height is small or not
				if ($this->height < $level)
				{
					//When gets a new long height
					$this->height = $level;
					$this->result = $sum + $root->data;
				}
				else if ($this->height == $level && $this->result < $sum + $root->data)
				{
					//When Two depth are same and new result are larger
					$this->result = $sum + $root->data;
				}
			}
		}
	}
	//function which is handling the request of calculating longest path sum
	public	function longest_path_sum()
	{
		//Set default value
		$this->result = 0;
		$this->height = 0;
		$this->long_path_result($this->root, 0, 0);
		echo "Result : ". $this->result ."\n";
	}
}

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

			            1
			         /    \
			        2      5
			       / \    /  \
			      1   7  7    2
			         /    \    \
			        9      1   -3
			              / 
			            -7 
			*/
	//Insertion of binary tree nodes
	$obj->root = new Node(1);
	$obj->root->left = new Node(2);
	$obj->root->left->left = new Node(1);
	$obj->root->left->right = new Node(7);
	$obj->root->left->right->left = new Node(9);
	$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(-7);
	$obj->root->right->right->right = new Node(-3);
	$obj->longest_path_sum();
}
main();

Output

Result : 7
/* 
  Node Js Program 
  Find the sum of longest path from root to leaf node
 */
//Binary Tree node
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.height = 0;
		this.result = 0;
	}
	//Calculate sum of longest path in given binary tree
	long_path_result(root, sum, level)
	{
		if (root != null)
		{
			//Recursively calculating the value of height and sum of path
			this.long_path_result(root.left, sum + root.data, level + 1);
			this.long_path_result(root.right, sum + root.data, level + 1);
			//Check current root node is leaf or not
			if (root.left == null && root.right == null)
			{
				//Check previous calculate height is small or not
				if (this.height < level)
				{
					//When gets a new long height
					this.height = level;
					this.result = sum + root.data;
				}
				else if (this.height == level && this.result < sum + root.data)
				{
					//When Two depth are same and new result are larger
					this.result = sum + root.data;
				}
			}
		}
	}
	//function which is handling the request of calculating longest path sum
	longest_path_sum()
	{
		//Set default value
		this.result = 0;
		this.height = 0;
		this.long_path_result(this.root, 0, 0);
		process.stdout.write("Result : " + this.result + "\n");
	}
}

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

			            1
			         /    \
			        2      5
			       / \    /  \
			      1   7  7    2
			         /    \    \
			        9      1   -3
			              / 
			            -7 
			*/
	//Insertion of binary tree nodes
	obj.root = new Node(1);
	obj.root.left = new Node(2);
	obj.root.left.left = new Node(1);
	obj.root.left.right = new Node(7);
	obj.root.left.right.left = new Node(9);
	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(-7);
	obj.root.right.right.right = new Node(-3);
	obj.longest_path_sum();
}
main();

Output

Result : 7
#   Python 3 Program 
#   Find the sum of longest path from root to leaf node
#  

# Binary Tree node
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.height = 0
		self.result = 0
	
	# Calculate sum of longest path in given binary tree
	def long_path_result(self, root, sum, level) :
		if (root != None) :
			# Recursively calculating the value of height and sum of path
			self.long_path_result(root.left, sum + root.data, level + 1)
			self.long_path_result(root.right, sum + root.data, level + 1)
			# Check current root node is leaf or not
			if (root.left == None and root.right == None) :
				# Check previous calculate height is small or not
				if (self.height < level) :
					# When gets a new long height
					self.height = level
					self.result = sum + root.data
				
				elif(self.height == level and self.result < sum + root.data) :
					# When Two depth are same and new result are larger
					self.result = sum + root.data
				
			
		
	
	# function which is handling the request of calculating longest path sum
	def longest_path_sum(self) :
		# Set default value
		self.result = 0
		self.height = 0
		self.long_path_result(self.root, 0, 0)
		print("Result : ", self.result ,"\n", end = "")
	

def main() :
	# Make object of Binary Tree
	obj = BinaryTree()
	#   Construct Binary tree
	# 		-----------------------
	# 		            1
	# 		         /    \
	# 		        2      5
	# 		       / \    /  \
	# 		      1   7  7    2
	# 		         /    \    \
	# 		        9      1   -3
	# 		              / 
	# 		            -7 
	# 		
	
	# Insertion of binary tree nodes
	obj.root = Node(1)
	obj.root.left = Node(2)
	obj.root.left.left = Node(1)
	obj.root.left.right = Node(7)
	obj.root.left.right.left = Node(9)
	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(-7)
	obj.root.right.right.right = Node(-3)
	obj.longest_path_sum()

if __name__ == "__main__": main()

Output

Result :  7
#   Ruby Program 
#   Find the sum of longest path from root to leaf node

# Binary Tree node
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :left, :right
	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_reader :root, :height, :result
	attr_accessor :root, :height, :result

	def initialize()
	
		# set initial tree root to null
		self.root = nil
		self.height = 0
		self.result = 0
	end
	# Calculate sum of longest path in given binary tree
	def long_path_result(root, sum, level)
	
		if (root != nil)
		
			# Recursively calculating the value of height and sum of path
			self.long_path_result(root.left, sum + root.data, level + 1)
			self.long_path_result(root.right, sum + root.data, level + 1)
			# Check current root node is leaf or not
			if (root.left == nil && root.right == nil)
			
				# Check previous calculate height is small or not
				if (self.height < level)
				
					# When gets a new long height
					self.height = level
					self.result = sum + root.data
				elsif(self.height == level && self.result < sum + root.data)
				
					# When Two depth are same and new result are larger
					self.result = sum + root.data
				end
			end
		end
	end
	# function which is handling the request of calculating longest path sum
	def longest_path_sum()
	
		# Set default value
		self.result = 0
		self.height = 0
		self.long_path_result(self.root, 0, 0)
		print("Result : ", self.result ,"\n")
	end
end
def main()

	# Make object of Binary Tree
	obj = BinaryTree.new()
	#   Construct Binary tree
	# 		-----------------------
	# 		            1
	# 		         /    \
	# 		        2      5
	# 		       / \    /  \
	# 		      1   7  7    2
	# 		         /    \    \
	# 		        9      1   -3
	# 		              / 
	# 		            -7 
	# 		
	
	# Insertion of binary tree nodes
	obj.root = Node.new(1)
	obj.root.left = Node.new(2)
	obj.root.left.left = Node.new(1)
	obj.root.left.right = Node.new(7)
	obj.root.left.right.left = Node.new(9)
	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(-7)
	obj.root.right.right.right = Node.new(-3)
	obj.longest_path_sum()
end
main()

Output

Result : 7
/* 
  Scala Program 
  Find the sum of longest path from root to leaf node
 */

//Binary Tree node
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 height: Int,
		var result: Int)
{
	def this()
	{
		this(null, 0, 0);
	}
	//Calculate sum of longest path in given binary tree
	def long_path_result(root: Node, sum: Int, level: Int): Unit = {
		if (root != null)
		{
			//Recursively calculating the value of height and sum of path
			long_path_result(root.left, sum + root.data, level + 1);
			long_path_result(root.right, sum + root.data, level + 1);
			//Check current root node is leaf or not
			if (root.left == null && root.right == null)
			{
				//Check previous calculate height is small or not
				if (this.height < level)
				{
					//When gets a new long height
					this.height = level;
					this.result = sum + root.data;
				}
				else if (this.height == level && this.result < sum + root.data)
				{
					//When Two depth are same and new result are larger
					this.result = sum + root.data;
				}
			}
		}
	}
	//function which is handling the request of calculating longest path sum
	def longest_path_sum(): Unit = {
		//Set default value
		this.result = 0;
		this.height = 0;
		long_path_result(this.root, 0, 0);
		print("Result : " + this.result + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		//Make object of Binary Tree
		var obj: BinaryTree = new BinaryTree();
		/*  Construct Binary tree
				-----------------------

				            1
				         /    \
				        2      5
				       / \    /  \
				      1   7  7    2
				         /    \    \
				        9      1   -3
				              / 
				            -7 
		*/
		//Insertion of binary tree nodes
		obj.root = new Node(1);
		obj.root.left = new Node(2);
		obj.root.left.left = new Node(1);
		obj.root.left.right = new Node(7);
		obj.root.left.right.left = new Node(9);
		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(-7);
		obj.root.right.right.right = new Node(-3);
		obj.longest_path_sum();
	}
}

Output

Result : 7
/* 
  Swift 4 Program 
  Find the sum of longest path from root to leaf node
 */
//Binary Tree node
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 height: Int;
	var result: Int;
	init()
	{
		//set initial tree root to null
		self.root = nil;
		self.height = 0;
		self.result = 0;
	}
	//Calculate sum of longest path in given binary tree
	func long_path_result(_ root: Node? , _ sum : Int, _ level: Int)
	{
		if (root != nil)
		{
			//Recursively calculating the value of height and sum of path
			self.long_path_result(root!.left, sum + root!.data, level + 1);
			self.long_path_result(root!.right, sum + root!.data, level + 1);
			//Check current root node is leaf or not
			if (root!.left == nil && root!.right == nil)
			{
				//Check previous calculate height is small or not
				if (self.height < level)
				{
					//When gets a new long height
					self.height = level;
					self.result = sum + root!.data;
				}
				else if (self.height == level && self.result < sum + root!.data)
				{
					//When Two depth are same and new result are larger
					self.result = sum + root!.data;
				}
			}
		}
	}
	//function which is handling the request of calculating longest path sum
	func longest_path_sum()
	{
		//Set default value
		self.result = 0;
		self.height = 0;
		self.long_path_result(self.root, 0, 0);
		print("Result : ", self.result ,"\n", terminator: "");
	}
}
func main()
{
	//Make object of Binary Tree
	let obj: BinaryTree = BinaryTree();
	/*  Construct Binary tree
			-----------------------

			            1
			         /    \
			        2      5
			       / \    /  \
			      1   7  7    2
			         /    \    \
			        9      1   -3
			              / 
			            -7 
			*/
	//Insertion of binary tree nodes
	obj.root = Node(1);
	obj.root!.left = Node(2);
	obj.root!.left!.left = Node(1);
	obj.root!.left!.right = Node(7);
	obj.root!.left!.right!.left = Node(9);
	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(-7);
	obj.root!.right!.right!.right = Node(-3);
	obj.longest_path_sum();
}
main();

Output

Result :  7


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.

New Comment







© 2021, kalkicode.com, All rights reserved