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

Find maximum sum from root to leaf path

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 
	*/
	//Add nodes
	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 
		 */
		//Add nodes
		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 
	 */
	//Add nodes
	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 
		*/
		//Add nodes
		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 
			 */
	//Add nodes
	$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 
			 */
	//Add nodes
	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 
	# 		 
	
	# Add nodes
	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_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, :result
	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 
	# 		 
	
	# Add nodes
	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 
		*/
		//Add nodes
		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 
	*/
	//Add nodes
	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.

New Comment







© 2021, kalkicode.com, All rights reserved