Skip to main content

Maximum path sum from leaf to leaf

Here given code implementation process.

/*
    C Program 
    Maximum path sum from leaf to leaf
*/
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

// Tree Node
struct TreeNode
{
	int data;
	struct TreeNode *left;
	struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
	struct TreeNode *root;
};
// Create new tree
struct BinaryTree *new_tree()
{
	// Create dynamic node
	struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
	if (tree != NULL)
	{
		tree->root = NULL;
	}
	else
	{
		printf("Memory Overflow to Create tree Tree\n");
	}
	//return new tree
	return tree;
}
// returns a new node of tree
struct TreeNode *new_node(int data)
{
	// Create dynamic node
	struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		//Set data and pointer values
		node->data = data;
		node->left = NULL;
		node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return node;
}
// Find maximum path between two leaf nodes
int leafPath(struct TreeNode *node, int *max)
{
	if (node != NULL)
	{
		if (node->left == NULL && node->right == NULL)
		{
			return node->data;
		}
		// Through by recursion find leaf path of left and right subtree
		int a = leafPath(node->left, max) + node->data;
		int b = leafPath(node->right, max) + node->data;
		if ( *max < ((a + b) - node->data))
		{
			// When current node left and right subtree contains max sum leaf path
			*max = ((a + b) - node->data);
		}
		if (a > b)
		{
			// Select path of left subtree
			if ( *max < a)
			{
				*max = a;
			}
			return a;
		}
		else
		{
			// Select path of right subtree
			if ( *max < b)
			{
				*max = b;
			}
			return b;
		}
	}
	return 0;
}
// Handles the request to find sum of maximum path between two leaf nodes
void maxleafPath(struct TreeNode *root)
{
	if (root != NULL)
	{
		if (root->left != NULL && root->right != NULL)
		{
			// When two leaf nodes exist in given tree
			int max = INT_MIN;
			leafPath(root, & max);
			printf("\n Result : %d \n", max);
		}
		else
		{
			// Find internal nodes that have two children?
			struct TreeNode *node = NULL;
			// Choose a valid direction
			if (root->left != NULL)
			{
				node = root->left;
			}
			else
			{
				node = root->right;
			}
			// Find nodes that have two childrenThis
			while (node != NULL && (node->left == NULL || node->right == NULL))
			{
				if (node->left == NULL)
				{
					node = node->right;
				}
				else
				{
					node = node->left;
				}
			}
			if (node != NULL && node->left != NULL && node->right != NULL)
			{
				maxleafPath(node);
			}
			else
			{
				printf("\n Two leaf nodes are not exist \n");
			}
		}
	}
}
//Display pre order elements
void preorder(struct TreeNode *node)
{
	if (node != NULL)
	{
		//Print node value
		printf("  %d", node->data);
		preorder(node->left);
		preorder(node->right);
	}
}
int main()
{
	// Define trees
	struct BinaryTree *tree1 = new_tree();
	struct BinaryTree *tree2 = new_tree();
	struct BinaryTree *tree3 = new_tree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	           / \
	          1  -2  
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree1->root = new_node(1);
	tree1->root->left = new_node(2);
	tree1->root->right = new_node(3);
	tree1->root->left->left = new_node(3);
	tree1->root->left->right = new_node(4);
	tree1->root->left->right->left = new_node(-7);
	tree1->root->right->left = new_node(6);
	tree1->root->right->right = new_node(5);
	tree1->root->right->left->right = new_node(4);
	tree1->root->right->right->right = new_node(2);
	tree1->root->right->left->right->left = new_node(1);
	tree1->root->right->left->right->right = new_node(-2);
	preorder(tree1->root);
	maxleafPath(tree1->root);
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    4   5 8   7
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree2->root = new_node(1);
	tree2->root->left = new_node(2);
	tree2->root->left->left = new_node(4);
	tree2->root->left->right = new_node(5);
	tree2->root->right = new_node(3);
	tree2->root->right->left = new_node(8);
	tree2->root->right->right = new_node(7);
	preorder(tree2->root);
	maxleafPath(tree2->root);
	/*
	        1
	       /   
	      2     
	     / 
	    4   
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree3->root = new_node(1);
	tree3->root->left = new_node(2);
	tree3->root->left->left = new_node(3);
	preorder(tree3->root);
	maxleafPath(tree3->root);
	return 0;
}

Output

  1  2  3  4  -7  3  6  4  1  -2  5  2
 Result : 21
  1  2  4  5  3  8  7
 Result : 19
  1  2  3
 Two leaf nodes are not exist
/*
    Java Program 
    Maximum path sum from leaf to leaf
*/
// Tree Node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Binary Tree
public class BinaryTree
{
	public TreeNode root;
	public int max;
	public BinaryTree()
	{
		this.root = null;
		this.max = 0;
	}
	// Find maximum path between two leaf nodes
	public int leafPath(TreeNode node)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				return node.data;
			}
			// Through by recursion find leaf path of left and right subtree
			int a = leafPath(node.left) + node.data;
			int b = leafPath(node.right) + node.data;
			if (this.max < ((a + b) - node.data))
			{
				// When current node left and right subtree contains max sum leaf path
				this.max = ((a + b) - node.data);
			}
			if (a > b)
			{
				// Select path of left subtree
				if (this.max < a)
				{
					this.max = a;
				}
				return a;
			}
			else
			{
				// Select path of right subtree
				if (this.max < b)
				{
					this.max = b;
				}
				return b;
			}
		}
		return 0;
	}
	// Handles the request to find sum of maximum path between two leaf nodes
	public void maxleafPath(TreeNode node)
	{
		if (node != null)
		{
			if (node.left != null && node.right != null)
			{
				// When two leaf nodes exist in given tree
				this.max = Integer.MIN_VALUE;;
				// Find path sum
				leafPath(node);
				// Display calculated result
				System.out.print("\n Result : " + max + " \n");
			}
			else
			{
				// Find internal nodes that have two children?
				TreeNode temp = null;
				// Choose a valid direction
				if (root.left != null)
				{
					temp = root.left;
				}
				else
				{
					temp = root.right;
				}
				// Find nodes that have two children 
				while (temp != null && (temp.left == null || temp.right == null))
				{
					if (temp.left == null)
					{
						temp = temp.right;
					}
					else
					{
						temp = temp.left;
					}
				}
				if (temp != null && temp.left != null && temp.right != null)
				{
					maxleafPath(temp);
				}
				else
				{
					System.out.print("\n Two leaf nodes are not exist \n");
				}
			}
		}
	}
	//Display pre order elements
	public void preorder(TreeNode node)
	{
		if (node != null)
		{
			//Print node value
			System.out.print("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	public static void main(String[] args)
	{
		// Define trees
		BinaryTree tree1 = new BinaryTree();
		BinaryTree tree2 = new BinaryTree();
		BinaryTree tree3 = new BinaryTree();
		/*
		         1
		       /   \
		      2     3
		     / \   / \
		    3   4 6   5
		       /   \   \
		     -7     4   2
		           / \
		          1  -2  
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree1.root = new TreeNode(1);
		tree1.root.left = new TreeNode(2);
		tree1.root.right = new TreeNode(3);
		tree1.root.left.left = new TreeNode(3);
		tree1.root.left.right = new TreeNode(4);
		tree1.root.left.right.left = new TreeNode(-7);
		tree1.root.right.left = new TreeNode(6);
		tree1.root.right.right = new TreeNode(5);
		tree1.root.right.left.right = new TreeNode(4);
		tree1.root.right.right.right = new TreeNode(2);
		tree1.root.right.left.right.left = new TreeNode(1);
		tree1.root.right.left.right.right = new TreeNode(-2);
		tree1.preorder(tree1.root);
		tree1.maxleafPath(tree1.root);
		/*
		         1
		       /   \
		      2     3
		     / \   / \
		    4   5 8   7
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree2.root = new TreeNode(1);
		tree2.root.left = new TreeNode(2);
		tree2.root.left.left = new TreeNode(4);
		tree2.root.left.right = new TreeNode(5);
		tree2.root.right = new TreeNode(3);
		tree2.root.right.left = new TreeNode(8);
		tree2.root.right.right = new TreeNode(7);
		tree2.preorder(tree2.root);
		tree2.maxleafPath(tree2.root);
		/*
		        1
		       /   
		      2     
		     / 
		    4   
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree3.root = new TreeNode(1);
		tree3.root.left = new TreeNode(2);
		tree3.root.left.left = new TreeNode(3);
		tree3.preorder(tree3.root);
		tree3.maxleafPath(tree3.root);
	}
}

Output

  1  2  3  4  -7  3  6  4  1  -2  5  2
 Result : 21
  1  2  4  5  3  8  7
 Result : 19
  1  2  3
 Two leaf nodes are not exist
// Include header file
#include <iostream>
#include<limits.h>
using namespace std;
/*
    C++ Program 
    Maximum path sum from leaf to leaf
*/
// Tree Node
class TreeNode
{
	public: int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
// Binary Tree
class BinaryTree
{
	public: TreeNode *root;
	int max;
	BinaryTree()
	{
		this->root = NULL;
		this->max = 0;
	}
	// Find maximum path between two leaf nodes
	int leafPath(TreeNode *node)
	{
		if (node != NULL)
		{
			if (node->left == NULL && node->right == NULL)
			{
				return node->data;
			}
			// Through by recursion find leaf path of left and right subtree
			int a = this->leafPath(node->left) + node->data;
			int b = this->leafPath(node->right) + node->data;
			if (this->max < ((a + b) - node->data))
			{
				// When current node left and right subtree contains max sum leaf path
				this->max = ((a + b) - node->data);
			}
			if (a > b)
			{
				// Select path of left subtree
				if (this->max < a)
				{
					this->max = a;
				}
				return a;
			}
			else
			{
				// Select path of right subtree
				if (this->max < b)
				{
					this->max = b;
				}
				return b;
			}
		}
		return 0;
	}
	// Handles the request to find sum of maximum path between two leaf nodes
	void maxleafPath(TreeNode *node)
	{
		if (node != NULL)
		{
			if (node->left != NULL && node->right != NULL)
			{
				// When two leaf nodes exist in given tree
				this->max = INT_MIN;;
				// Find path sum
				this->leafPath(node);
				// Display calculated result
				cout << "\n Result : " << this->max << " \n";
			}
			else
			{
				// Find internal nodes that have two children?
				TreeNode *temp = NULL;
				// Choose a valid direction
				if (this->root->left != NULL)
				{
					temp = this->root->left;
				}
				else
				{
					temp = this->root->right;
				}
				// Find nodes that have two children
				while (temp != NULL && (temp->left == NULL || temp->right == NULL))
				{
					if (temp->left == NULL)
					{
						temp = temp->right;
					}
					else
					{
						temp = temp->left;
					}
				}
				if (temp != NULL && temp->left != NULL && temp->right != NULL)
				{
					this->maxleafPath(temp);
				}
				else
				{
					cout << "\n Two leaf nodes are not exist \n";
				}
			}
		}
	}
	//Display pre order elements
	void preorder(TreeNode *node)
	{
		if (node != NULL)
		{
			//Print node value
			cout << "  " << node->data;
			this->preorder(node->left);
			this->preorder(node->right);
		}
	}
};
int main()
{
	// Define trees
	BinaryTree tree1 = BinaryTree();
	BinaryTree tree2 = BinaryTree();
	BinaryTree tree3 = BinaryTree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	           / \
	          1  -2  
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree1.root = new TreeNode(1);
	tree1.root->left = new TreeNode(2);
	tree1.root->right = new TreeNode(3);
	tree1.root->left->left = new TreeNode(3);
	tree1.root->left->right = new TreeNode(4);
	tree1.root->left->right->left = new TreeNode(-7);
	tree1.root->right->left = new TreeNode(6);
	tree1.root->right->right = new TreeNode(5);
	tree1.root->right->left->right = new TreeNode(4);
	tree1.root->right->right->right = new TreeNode(2);
	tree1.root->right->left->right->left = new TreeNode(1);
	tree1.root->right->left->right->right = new TreeNode(-2);
	tree1.preorder(tree1.root);
	tree1.maxleafPath(tree1.root);
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    4   5 8   7
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree2.root = new TreeNode(1);
	tree2.root->left = new TreeNode(2);
	tree2.root->left->left = new TreeNode(4);
	tree2.root->left->right = new TreeNode(5);
	tree2.root->right = new TreeNode(3);
	tree2.root->right->left = new TreeNode(8);
	tree2.root->right->right = new TreeNode(7);
	tree2.preorder(tree2.root);
	tree2.maxleafPath(tree2.root);
	/*
	        1
	       /   
	      2     
	     / 
	    4   
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree3.root = new TreeNode(1);
	tree3.root->left = new TreeNode(2);
	tree3.root->left->left = new TreeNode(3);
	tree3.preorder(tree3.root);
	tree3.maxleafPath(tree3.root);
	return 0;
}

Output

  1  2  3  4  -7  3  6  4  1  -2  5  2
 Result : 21
  1  2  4  5  3  8  7
 Result : 19
  1  2  3
 Two leaf nodes are not exist
// Include namespace system
using System;
/*
    C# Program 
    Maximum path sum from leaf to leaf
*/
// Tree Node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Binary Tree
public class BinaryTree
{
	public TreeNode root;
	public int max;
	public BinaryTree()
	{
		this.root = null;
		this.max = 0;
	}
	// Find maximum path between two leaf nodes
	public int leafPath(TreeNode node)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				return node.data;
			}
			// Through by recursion find leaf path of left and right subtree
			int a = leafPath(node.left) + node.data;
			int b = leafPath(node.right) + node.data;
			if (this.max < ((a + b) - node.data))
			{
				// When current node left and right subtree contains max sum leaf path
				this.max = ((a + b) - node.data);
			}
			if (a > b)
			{
				// Select path of left subtree
				if (this.max < a)
				{
					this.max = a;
				}
				return a;
			}
			else
			{
				// Select path of right subtree
				if (this.max < b)
				{
					this.max = b;
				}
				return b;
			}
		}
		return 0;
	}
	// Handles the request to find sum of maximum path between two leaf nodes
	public void maxleafPath(TreeNode node)
	{
		if (node != null)
		{
			if (node.left != null && node.right != null)
			{
				// When two leaf nodes exist in given tree
				this.max = int.MinValue;;
				// Find path sum
				leafPath(node);
				// Display calculated result
				Console.Write("\n Result : " + max + " \n");
			}
			else
			{
				// Find internal nodes that have two children?
				TreeNode temp = null;
				// Choose a valid direction
				if (root.left != null)
				{
					temp = root.left;
				}
				else
				{
					temp = root.right;
				}
				// Find nodes that have two children
				while (temp != null && (temp.left == null || temp.right == null))
				{
					if (temp.left == null)
					{
						temp = temp.right;
					}
					else
					{
						temp = temp.left;
					}
				}
				if (temp != null && temp.left != null && temp.right != null)
				{
					maxleafPath(temp);
				}
				else
				{
					Console.Write("\n Two leaf nodes are not exist \n");
				}
			}
		}
	}
	//Display pre order elements
	public void preorder(TreeNode node)
	{
		if (node != null)
		{
			//Print node value
			Console.Write("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	public static void Main(String[] args)
	{
		// Define trees
		BinaryTree tree1 = new BinaryTree();
		BinaryTree tree2 = new BinaryTree();
		BinaryTree tree3 = new BinaryTree();
		/*
		         1
		       /   \
		      2     3
		     / \   / \
		    3   4 6   5
		       /   \   \
		     -7     4   2
		           / \
		          1  -2  
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree1.root = new TreeNode(1);
		tree1.root.left = new TreeNode(2);
		tree1.root.right = new TreeNode(3);
		tree1.root.left.left = new TreeNode(3);
		tree1.root.left.right = new TreeNode(4);
		tree1.root.left.right.left = new TreeNode(-7);
		tree1.root.right.left = new TreeNode(6);
		tree1.root.right.right = new TreeNode(5);
		tree1.root.right.left.right = new TreeNode(4);
		tree1.root.right.right.right = new TreeNode(2);
		tree1.root.right.left.right.left = new TreeNode(1);
		tree1.root.right.left.right.right = new TreeNode(-2);
		tree1.preorder(tree1.root);
		tree1.maxleafPath(tree1.root);
		/*
		         1
		       /   \
		      2     3
		     / \   / \
		    4   5 8   7
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree2.root = new TreeNode(1);
		tree2.root.left = new TreeNode(2);
		tree2.root.left.left = new TreeNode(4);
		tree2.root.left.right = new TreeNode(5);
		tree2.root.right = new TreeNode(3);
		tree2.root.right.left = new TreeNode(8);
		tree2.root.right.right = new TreeNode(7);
		tree2.preorder(tree2.root);
		tree2.maxleafPath(tree2.root);
		/*
		        1
		       /   
		      2     
		     / 
		    4   
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree3.root = new TreeNode(1);
		tree3.root.left = new TreeNode(2);
		tree3.root.left.left = new TreeNode(3);
		tree3.preorder(tree3.root);
		tree3.maxleafPath(tree3.root);
	}
}

Output

  1  2  3  4  -7  3  6  4  1  -2  5  2
 Result : 21
  1  2  4  5  3  8  7
 Result : 19
  1  2  3
 Two leaf nodes are not exist
<?php
/*
    Php Program 
    Maximum path sum from leaf to leaf
*/
// Tree Node
class TreeNode
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
// Binary Tree
class BinaryTree
{
	public $root;
	public $max;

	function __construct()
	{
		$this->root = null;
		$this->max = 0;
	}
	// Find maximum path between two leaf nodes
	public	function leafPath($node)
	{
		if ($node != null)
		{
			if ($node->left == null && $node->right == null)
			{
				return $node->data;
			}
			// Through by recursion find leaf path of left and right subtree
			$a = $this->leafPath($node->left) + $node->data;
			$b = $this->leafPath($node->right) + $node->data;
			if ($this->max < (($a + $b) - $node->data))
			{
				// When current node left and right subtree contains max sum leaf path
				$this->max = (($a + $b) - $node->data);
			}
			if ($a > $b)
			{
				// Select path of left subtree
				if ($this->max < $a)
				{
					$this->max = $a;
				}
				return $a;
			}
			else
			{
				// Select path of right subtree
				if ($this->max < $b)
				{
					$this->max = $b;
				}
				return $b;
			}
		}
		return 0;
	}
	// Handles the request to find sum of maximum path between two leaf nodes
	public	function maxleafPath($node)
	{
		if ($node != null)
		{
			if ($node->left != null && $node->right != null)
			{
				// When two leaf nodes exist in given tree
				$this->max = -PHP_INT_MAX;;
				// Find path sum
				$this->leafPath($node);
				// Display calculated result
				echo "\n Result : ". $this->max ." \n";
			}
			else
			{
				// Find internal nodes that have two children?
				$temp = null;
				// Choose a valid direction
				if ($this->root->left != null)
				{
					$temp = $this->root->left;
				}
				else
				{
					$temp = $this->root->right;
				}
				// Find nodes that have two children
				while ($temp != null && ($temp->left == null || $temp->right == null))
				{
					if ($temp->left == null)
					{
						$temp = $temp->right;
					}
					else
					{
						$temp = $temp->left;
					}
				}
				if ($temp != null && $temp->left != null && $temp->right != null)
				{
					$this->maxleafPath($temp);
				}
				else
				{
					echo "\n Two leaf nodes are not exist \n";
				}
			}
		}
	}
	//Display pre order elements
	public	function preorder($node)
	{
		if ($node != null)
		{
			//Print node value
			echo "  ". $node->data;
			$this->preorder($node->left);
			$this->preorder($node->right);
		}
	}
}

function main()
{
	// Define trees
	$tree1 = new BinaryTree();
	$tree2 = new BinaryTree();
	$tree3 = new BinaryTree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	           / \
	          1  -2  
	-----------------------
	    Binary Tree
	-----------------------
	*/
	$tree1->root = new TreeNode(1);
	$tree1->root->left = new TreeNode(2);
	$tree1->root->right = new TreeNode(3);
	$tree1->root->left->left = new TreeNode(3);
	$tree1->root->left->right = new TreeNode(4);
	$tree1->root->left->right->left = new TreeNode(-7);
	$tree1->root->right->left = new TreeNode(6);
	$tree1->root->right->right = new TreeNode(5);
	$tree1->root->right->left->right = new TreeNode(4);
	$tree1->root->right->right->right = new TreeNode(2);
	$tree1->root->right->left->right->left = new TreeNode(1);
	$tree1->root->right->left->right->right = new TreeNode(-2);
	$tree1->preorder($tree1->root);
	$tree1->maxleafPath($tree1->root);
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    4   5 8   7
	-----------------------
	    Binary Tree
	-----------------------
	*/
	$tree2->root = new TreeNode(1);
	$tree2->root->left = new TreeNode(2);
	$tree2->root->left->left = new TreeNode(4);
	$tree2->root->left->right = new TreeNode(5);
	$tree2->root->right = new TreeNode(3);
	$tree2->root->right->left = new TreeNode(8);
	$tree2->root->right->right = new TreeNode(7);
	$tree2->preorder($tree2->root);
	$tree2->maxleafPath($tree2->root);
	/*
	        1
	       /   
	      2     
	     / 
	    4   
	-----------------------
	    Binary Tree
	-----------------------
	*/
	$tree3->root = new TreeNode(1);
	$tree3->root->left = new TreeNode(2);
	$tree3->root->left->left = new TreeNode(3);
	$tree3->preorder($tree3->root);
	$tree3->maxleafPath($tree3->root);
}
main();

Output

  1  2  3  4  -7  3  6  4  1  -2  5  2
 Result : 21
  1  2  4  5  3  8  7
 Result : 19
  1  2  3
 Two leaf nodes are not exist
/*
    Node Js Program 
    Maximum path sum from leaf to leaf
*/
// Tree Node
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Binary Tree
class BinaryTree
{
	constructor()
	{
		this.root = null;
		this.max = 0;
	}
	// Find maximum path between two leaf nodes
	leafPath(node)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				return node.data;
			}
			// Through by recursion find leaf path of left and right subtree
			var a = this.leafPath(node.left) + node.data;
			var b = this.leafPath(node.right) + node.data;
			if (this.max < ((a + b) - node.data))
			{
				// When current node left and right subtree contains max sum leaf path
				this.max = ((a + b) - node.data);
			}
			if (a > b)
			{
				// Select path of left subtree
				if (this.max < a)
				{
					this.max = a;
				}
				return a;
			}
			else
			{
				// Select path of right subtree
				if (this.max < b)
				{
					this.max = b;
				}
				return b;
			}
		}
		return 0;
	}
	// Handles the request to find sum of maximum path between two leaf nodes
	maxleafPath(node)
	{
		if (node != null)
		{
			if (node.left != null && node.right != null)
			{
				// When two leaf nodes exist in given tree
				this.max = -Number.MAX_VALUE;;
				// Find path sum
				this.leafPath(node);
				// Display calculated result
				process.stdout.write("\n Result : " + this.max + " \n");
			}
			else
			{
				// Find internal nodes that have two children?
				var temp = null;
				// Choose a valid direction
				if (this.root.left != null)
				{
					temp = this.root.left;
				}
				else
				{
					temp = this.root.right;
				}
				// Find nodes that have two children
				while (temp != null && (temp.left == null || temp.right == null))
				{
					if (temp.left == null)
					{
						temp = temp.right;
					}
					else
					{
						temp = temp.left;
					}
				}
				if (temp != null && temp.left != null && temp.right != null)
				{
					this.maxleafPath(temp);
				}
				else
				{
					process.stdout.write("\n Two leaf nodes are not exist \n");
				}
			}
		}
	}
	//Display pre order elements
	preorder(node)
	{
		if (node != null)
		{
			//Print node value
			process.stdout.write("  " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
}

function main()
{
	// Define trees
	var tree1 = new BinaryTree();
	var tree2 = new BinaryTree();
	var tree3 = new BinaryTree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	           / \
	          1  -2  
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree1.root = new TreeNode(1);
	tree1.root.left = new TreeNode(2);
	tree1.root.right = new TreeNode(3);
	tree1.root.left.left = new TreeNode(3);
	tree1.root.left.right = new TreeNode(4);
	tree1.root.left.right.left = new TreeNode(-7);
	tree1.root.right.left = new TreeNode(6);
	tree1.root.right.right = new TreeNode(5);
	tree1.root.right.left.right = new TreeNode(4);
	tree1.root.right.right.right = new TreeNode(2);
	tree1.root.right.left.right.left = new TreeNode(1);
	tree1.root.right.left.right.right = new TreeNode(-2);
	tree1.preorder(tree1.root);
	tree1.maxleafPath(tree1.root);
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    4   5 8   7
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree2.root = new TreeNode(1);
	tree2.root.left = new TreeNode(2);
	tree2.root.left.left = new TreeNode(4);
	tree2.root.left.right = new TreeNode(5);
	tree2.root.right = new TreeNode(3);
	tree2.root.right.left = new TreeNode(8);
	tree2.root.right.right = new TreeNode(7);
	tree2.preorder(tree2.root);
	tree2.maxleafPath(tree2.root);
	/*
	        1
	       /   
	      2     
	     / 
	    4   
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree3.root = new TreeNode(1);
	tree3.root.left = new TreeNode(2);
	tree3.root.left.left = new TreeNode(3);
	tree3.preorder(tree3.root);
	tree3.maxleafPath(tree3.root);
}
main();

Output

  1  2  3  4  -7  3  6  4  1  -2  5  2
 Result : 21
  1  2  4  5  3  8  7
 Result : 19
  1  2  3
 Two leaf nodes are not exist
import sys

#   Python 3 Program 
#   Maximum path sum from leaf to leaf

#  Tree Node
class TreeNode :
	
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

#  Binary Tree
class BinaryTree :
	
	def __init__(self) :
		self.root = None
		self.max = 0
	
	#  Find maximum path between two leaf nodes
	def leafPath(self, node) :
		if (node != None) :
			if (node.left == None and node.right == None) :
				return node.data
			
			#  Through by recursion find leaf path of left and right subtree
			a = self.leafPath(node.left) + node.data
			b = self.leafPath(node.right) + node.data
			if (self.max < ((a + b) - node.data)) :
				#  When current node left and right subtree contains max sum leaf path
				self.max = ((a + b) - node.data)
			
			if (a > b) :
				#  Select path of left subtree
				if (self.max < a) :
					self.max = a
				
				return a
			else :
				#  Select path of right subtree
				if (self.max < b) :
					self.max = b
				
				return b
			
		
		return 0
	
	#  Handles the request to find sum of maximum path between two leaf nodes
	def maxleafPath(self, node) :
		if (node != None) :
			if (node.left != None and node.right != None) :
				#  When two leaf nodes exist in given tree
				self.max = -sys.maxsize
				#  Find path sum
				self.leafPath(node)
				#  Display calculated result
				print("\n Result : ", self.max ," ")
			else :
				#  Find internal nodes that have two children?
				temp = None
				#  Choose a valid direction
				if (self.root.left != None) :
					temp = self.root.left
				else :
					temp = self.root.right
				
				#  Find nodes that have two children
				while (temp != None and(temp.left == None or temp.right == None)) :
					if (temp.left == None) :
						temp = temp.right
					else :
						temp = temp.left
					
				
				if (temp != None and temp.left != None and temp.right != None) :
					self.maxleafPath(temp)
				else :
					print("\n Two leaf nodes are not exist ")
				
			
		
	
	# Display pre order elements
	def preorder(self, node) :
		if (node != None) :
			# Print node value
			print("  ", node.data, end = "")
			self.preorder(node.left)
			self.preorder(node.right)
		
	

def main() :
	#  Define trees
	tree1 = BinaryTree()
	tree2 = BinaryTree()
	tree3 = BinaryTree()
	# 
	#          1
	#        /   \
	#       2     3
	#      / \   / \
	#     3   4 6   5
	#        /   \   \
	#      -7     4   2
	#            / \
	#           1  -2  
	# -----------------------
	#     Binary Tree
	# -----------------------
	
	tree1.root = TreeNode(1)
	tree1.root.left = TreeNode(2)
	tree1.root.right = TreeNode(3)
	tree1.root.left.left = TreeNode(3)
	tree1.root.left.right = TreeNode(4)
	tree1.root.left.right.left = TreeNode(-7)
	tree1.root.right.left = TreeNode(6)
	tree1.root.right.right = TreeNode(5)
	tree1.root.right.left.right = TreeNode(4)
	tree1.root.right.right.right = TreeNode(2)
	tree1.root.right.left.right.left = TreeNode(1)
	tree1.root.right.left.right.right = TreeNode(-2)
	tree1.preorder(tree1.root)
	tree1.maxleafPath(tree1.root)
	# 
	#          1
	#        /   \
	#       2     3
	#      / \   / \
	#     4   5 8   7
	# -----------------------
	#     Binary Tree
	# -----------------------
	
	tree2.root = TreeNode(1)
	tree2.root.left = TreeNode(2)
	tree2.root.left.left = TreeNode(4)
	tree2.root.left.right = TreeNode(5)
	tree2.root.right = TreeNode(3)
	tree2.root.right.left = TreeNode(8)
	tree2.root.right.right = TreeNode(7)
	tree2.preorder(tree2.root)
	tree2.maxleafPath(tree2.root)
	# 
	#         1
	#        /   
	#       2     
	#      / 
	#     4   
	# -----------------------
	#     Binary Tree
	# -----------------------
	
	tree3.root = TreeNode(1)
	tree3.root.left = TreeNode(2)
	tree3.root.left.left = TreeNode(3)
	tree3.preorder(tree3.root)
	tree3.maxleafPath(tree3.root)

if __name__ == "__main__": main()

Output

   1   2   3   4   -7   3   6   4   1   -2   5   2
 Result :  21
   1   2   4   5   3   8   7
 Result :  19
   1   2   3
 Two leaf nodes are not exist
#  Ruby Program 
#  Maximum path sum from leaf to leaf

#  Tree Node
class TreeNode  
	# Define the accessor and reader of class TreeNode  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
 
	
	def initialize(data) 
		self.data = data
		self.left = nil
		self.right = nil
	end

end

#  Binary Tree
class BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root, :max
	attr_accessor :root, :max
 
	
	def initialize() 
		self.root = nil
		self.max = 0
	end

	#  Find maximum path between two leaf nodes
	def leafPath(node) 
		if (node != nil) 
			if (node.left == nil && node.right == nil) 
				return node.data
			end

			#  Through by recursion find leaf path of left and right subtree
			a = self.leafPath(node.left) + node.data
			b = self.leafPath(node.right) + node.data
			if (self.max < ((a + b) - node.data)) 
				#  When current node left and right subtree contains max sum leaf path
				self.max = ((a + b) - node.data)
			end

			if (a > b) 
				#  Select path of left subtree
				if (self.max < a) 
					self.max = a
				end

				return a
			else 
				#  Select path of right subtree
				if (self.max < b) 
					self.max = b
				end

				return b
			end

		end

		return 0
	end

	#  Handles the request to find sum of maximum path between two leaf nodes
	def maxleafPath(node) 
		if (node != nil) 
			if (node.left != nil && node.right != nil) 
				#  When two leaf nodes exist in given tree
				self.max = -(2 ** (0. size * 8 - 2))
				#  Find path sum
				self.leafPath(node)
				#  Display calculated result
				print("\n Result : ", max ," \n")
			else 
				#  Find internal nodes that have two children?
				temp = nil
				#  Choose a valid direction
				if (root.left != nil) 
					temp = root.left
				else 
					temp = root.right
				end

				#  Find nodes that have two children
				while (temp != nil && (temp.left == nil || temp.right == nil)) 
					if (temp.left == nil) 
						temp = temp.right
					else 
						temp = temp.left
					end

				end

				if (temp != nil && temp.left != nil && temp.right != nil) 
					self.maxleafPath(temp)
				else 
					print("\n Two leaf nodes are not exist \n")
				end

			end

		end

	end

	# Display pre order elements
	def preorder(node) 
		if (node != nil) 
			# Print node value
			print("  ", node.data)
			self.preorder(node.left)
			self.preorder(node.right)
		end

	end

end

def main() 
	#  Define trees
	tree1 = BinaryTree.new()
	tree2 = BinaryTree.new()
	tree3 = BinaryTree.new()
	# 
	#          1
	#        /   \
	#       2     3
	#      / \   / \
	#     3   4 6   5
	#        /   \   \
	#      -7     4   2
	#            / \
	#           1  -2  
	# -----------------------
	#     Binary Tree
	# -----------------------
	
	tree1.root = TreeNode.new(1)
	tree1.root.left = TreeNode.new(2)
	tree1.root.right = TreeNode.new(3)
	tree1.root.left.left = TreeNode.new(3)
	tree1.root.left.right = TreeNode.new(4)
	tree1.root.left.right.left = TreeNode.new(-7)
	tree1.root.right.left = TreeNode.new(6)
	tree1.root.right.right = TreeNode.new(5)
	tree1.root.right.left.right = TreeNode.new(4)
	tree1.root.right.right.right = TreeNode.new(2)
	tree1.root.right.left.right.left = TreeNode.new(1)
	tree1.root.right.left.right.right = TreeNode.new(-2)
	tree1.preorder(tree1.root)
	tree1.maxleafPath(tree1.root)
	# 
	#          1
	#        /   \
	#       2     3
	#      / \   / \
	#     4   5 8   7
	# -----------------------
	#     Binary Tree
	# -----------------------
	
	tree2.root = TreeNode.new(1)
	tree2.root.left = TreeNode.new(2)
	tree2.root.left.left = TreeNode.new(4)
	tree2.root.left.right = TreeNode.new(5)
	tree2.root.right = TreeNode.new(3)
	tree2.root.right.left = TreeNode.new(8)
	tree2.root.right.right = TreeNode.new(7)
	tree2.preorder(tree2.root)
	tree2.maxleafPath(tree2.root)
	# 
	#         1
	#        /   
	#       2     
	#      / 
	#     4   
	# -----------------------
	#     Binary Tree
	# -----------------------
	
	tree3.root = TreeNode.new(1)
	tree3.root.left = TreeNode.new(2)
	tree3.root.left.left = TreeNode.new(3)
	tree3.preorder(tree3.root)
	tree3.maxleafPath(tree3.root)
end

main()

Output

  1  2  3  4  -7  3  6  4  1  -2  5  2
 Result : 21 
  1  2  4  5  3  8  7
 Result : 19 
  1  2  3
 Two leaf nodes are not exist 
/*
    Scala Program 
    Maximum path sum from leaf to leaf
*/
// Tree Node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
// Binary Tree
class BinaryTree(var root: TreeNode , var max: Int)
{
	def this()
	{
		this(null, 0);
	}
	// Find maximum path between two leaf nodes
	def leafPath(node: TreeNode): Int = {
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				return node.data;
			}
			// Through by recursion find leaf path of left and right subtree
			var a: Int = this.leafPath(node.left) + node.data;
			var b: Int = this.leafPath(node.right) + node.data;
			if (this.max < ((a + b) - node.data))
			{
				// When current node left and right subtree contains max sum leaf path
				this.max = ((a + b) - node.data);
			}
			if (a > b)
			{
				// Select path of left subtree
				if (this.max < a)
				{
					this.max = a;
				}
				return a;
			}
			else
			{
				// Select path of right subtree
				if (this.max < b)
				{
					this.max = b;
				}
				return b;
			}
		}
		return 0;
	}
	// Handles the request to find sum of maximum path between two leaf nodes
	def maxleafPath(node: TreeNode): Unit = {
		if (node != null)
		{
			if (node.left != null && node.right != null)
			{
				// When two leaf nodes exist in given tree
				this.max = Int.MinValue;;
				// Find path sum
				this.leafPath(node);
				// Display calculated result
				print("\n Result : " + max + " \n");
			}
			else
			{
				// Find internal nodes that have two children?
				var temp: TreeNode = null;
				// Choose a valid direction
				if (root.left != null)
				{
					temp = root.left;
				}
				else
				{
					temp = root.right;
				}
				// Find nodes that have two children
				while (temp != null && (temp.left == null || temp.right == null))
				{
					if (temp.left == null)
					{
						temp = temp.right;
					}
					else
					{
						temp = temp.left;
					}
				}
				if (temp != null && temp.left != null && temp.right != null)
				{
					this.maxleafPath(temp);
				}
				else
				{
					print("\n Two leaf nodes are not exist \n");
				}
			}
		}
	}
	//Display pre order elements
	def preorder(node: TreeNode): Unit = {
		if (node != null)
		{
			//Print node value
			print("  " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Define trees
		var tree1: BinaryTree = new BinaryTree();
		var tree2: BinaryTree = new BinaryTree();
		var tree3: BinaryTree = new BinaryTree();
		/*
		         1
		       /   \
		      2     3
		     / \   / \
		    3   4 6   5
		       /   \   \
		     -7     4   2
		           / \
		          1  -2  
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree1.root = new TreeNode(1);
		tree1.root.left = new TreeNode(2);
		tree1.root.right = new TreeNode(3);
		tree1.root.left.left = new TreeNode(3);
		tree1.root.left.right = new TreeNode(4);
		tree1.root.left.right.left = new TreeNode(-7);
		tree1.root.right.left = new TreeNode(6);
		tree1.root.right.right = new TreeNode(5);
		tree1.root.right.left.right = new TreeNode(4);
		tree1.root.right.right.right = new TreeNode(2);
		tree1.root.right.left.right.left = new TreeNode(1);
		tree1.root.right.left.right.right = new TreeNode(-2);
		tree1.preorder(tree1.root);
		tree1.maxleafPath(tree1.root);
		/*
		         1
		       /   \
		      2     3
		     / \   / \
		    4   5 8   7
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree2.root = new TreeNode(1);
		tree2.root.left = new TreeNode(2);
		tree2.root.left.left = new TreeNode(4);
		tree2.root.left.right = new TreeNode(5);
		tree2.root.right = new TreeNode(3);
		tree2.root.right.left = new TreeNode(8);
		tree2.root.right.right = new TreeNode(7);
		tree2.preorder(tree2.root);
		tree2.maxleafPath(tree2.root);
		/*
		        1
		       /   
		      2     
		     / 
		    4   
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree3.root = new TreeNode(1);
		tree3.root.left = new TreeNode(2);
		tree3.root.left.left = new TreeNode(3);
		tree3.preorder(tree3.root);
		tree3.maxleafPath(tree3.root);
	}
}

Output

  1  2  3  4  -7  3  6  4  1  -2  5  2
 Result : 21
  1  2  4  5  3  8  7
 Result : 19
  1  2  3
 Two leaf nodes are not exist
/*
    Swift 4 Program 
    Maximum path sum from leaf to leaf
*/
// Tree Node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
// Binary Tree
class BinaryTree
{
	var root: TreeNode? ;
	var max: Int;
	init()
	{
		self.root = nil;
		self.max = 0;
	}
	// Find maximum path between two leaf nodes
	func leafPath(_ node: TreeNode? )->Int
	{
		if (node  != nil)
		{
			if (node!.left == nil && node!.right == nil)
			{
				return node!.data;
			}
			// Through by recursion find leaf path of left and right subtree
			let a: Int = self.leafPath(node!.left) + node!.data;
			let b: Int = self.leafPath(node!.right) + node!.data;
			if (self.max < ((a + b) - node!.data))
			{
				// When current node left and right subtree contains max sum leaf path
				self.max = ((a + b) - node!.data);
			}
			if (a > b)
			{
				// Select path of left subtree
				if (self.max < a)
				{
					self.max = a;
				}
				return a;
			}
			else
			{
				// Select path of right subtree
				if (self.max < b)
				{
					self.max = b;
				}
				return b;
			}
		}
		return 0;
	}
	// Handles the request to find sum of maximum path between two leaf nodes
	func maxleafPath(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			if (node!.left  != nil && node!.right  != nil)
			{
				// When two leaf nodes exist in given tree
				self.max = Int.min;
				// Find path sum
				let _ = self.leafPath(node);
				// Display calculated result
				print("\n Result : ", self.max ," ");
			}
			else
			{
				// Find internal nodes that have two children?
				var temp: TreeNode? = nil;
				// Choose a valid direction
				if (self.root!.left  != nil)
				{
					temp = self.root!.left;
				}
				else
				{
					temp = self.root!.right;
				}
				// Find nodes that have two children
				while (temp  != nil && (temp!.left == nil || temp!.right == nil))
				{
					if (temp!.left == nil)
					{
						temp = temp!.right;
					}
					else
					{
						temp = temp!.left;
					}
				}
				if (temp  != nil && temp!.left  != nil && temp!.right  != nil)
				{
					self.maxleafPath(temp);
				}
				else
				{
					print("\n Two leaf nodes are not exist ");
				}
			}
		}
	}
	//Display pre order elements
	func preorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			//Print node value
			print("  ", node!.data, terminator: "");
			self.preorder(node!.left);
			self.preorder(node!.right);
		}
	}
}
func main()
{
	// Define trees
	let tree1: BinaryTree = BinaryTree();
	let tree2: BinaryTree = BinaryTree();
	let tree3: BinaryTree = BinaryTree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	           / \
	          1  -2  
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree1.root = TreeNode(1);
	tree1.root!.left = TreeNode(2);
	tree1.root!.right = TreeNode(3);
	tree1.root!.left!.left = TreeNode(3);
	tree1.root!.left!.right = TreeNode(4);
	tree1.root!.left!.right!.left = TreeNode(-7);
	tree1.root!.right!.left = TreeNode(6);
	tree1.root!.right!.right = TreeNode(5);
	tree1.root!.right!.left!.right = TreeNode(4);
	tree1.root!.right!.right!.right = TreeNode(2);
	tree1.root!.right!.left!.right!.left = TreeNode(1);
	tree1.root!.right!.left!.right!.right = TreeNode(-2);
	tree1.preorder(tree1.root);
	tree1.maxleafPath(tree1.root);
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    4   5 8   7
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree2.root = TreeNode(1);
	tree2.root!.left = TreeNode(2);
	tree2.root!.left!.left = TreeNode(4);
	tree2.root!.left!.right = TreeNode(5);
	tree2.root!.right = TreeNode(3);
	tree2.root!.right!.left = TreeNode(8);
	tree2.root!.right!.right = TreeNode(7);
	tree2.preorder(tree2.root);
	tree2.maxleafPath(tree2.root);
	/*
	        1
	       /   
	      2     
	     / 
	    4   
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree3.root = TreeNode(1);
	tree3.root!.left = TreeNode(2);
	tree3.root!.left!.left = TreeNode(3);
	tree3.preorder(tree3.root);
	tree3.maxleafPath(tree3.root);
}
main();

Output

   1   2   3   4   -7   3   6   4   1   -2   5   2
 Result :  21
   1   2   4   5   3   8   7
 Result :  19
   1   2   3
 Two leaf nodes are not exist
/*
    Kotlin Program 
    Maximum path sum from leaf to leaf
*/
// Tree Node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	constructor(data: Int)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Binary Tree
class BinaryTree
{
	var root: TreeNode ? ;
	var max: Int;
	constructor()
	{
		this.root = null;
		this.max = 0;
	}
	// Find maximum path between two leaf nodes
	fun leafPath(node: TreeNode? ): Int
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				return node.data;
			}
			// Through by recursion find leaf path of left and right subtree
			var a: Int = this.leafPath(node.left) + node.data;
			var b: Int = this.leafPath(node.right) + node.data;
			if (this.max < ((a + b) - node.data))
			{
				// When current node left and right subtree contains max sum leaf path
				this.max = ((a + b) - node.data);
			}
			if (a > b)
			{
				// Select path of left subtree
				if (this.max < a)
				{
					this.max = a;
				}
				return a;
			}
			else
			{
				// Select path of right subtree
				if (this.max < b)
				{
					this.max = b;
				}
				return b;
			}
		}
		return 0;
	}
	// Handles the request to find sum of maximum path between two leaf nodes
	fun maxleafPath(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			if (node.left != null && node.right != null)
			{
				// When two leaf nodes exist in given tree
				this.max = Int.MIN_VALUE;
				// Find path sum
				this.leafPath(node);
				// Display calculated result
				print("\n Result : " + max + " \n");
			}
			else
			{
				// Find internal nodes that have two children?
				var temp: TreeNode?;
				// Choose a valid direction
				if (root?.left != null)
				{
					temp = root?.left;
				}
				else
				{
					temp = root?.right;
				}
				// Find nodes that have two children
				while (temp != null && (temp.left == null || temp.right == null))
				{
					if (temp.left == null)
					{
						temp = temp.right;
					}
					else
					{
						temp = temp.left;
					}
				}
				if (temp != null && temp.left != null && temp.right != null)
				{
					this.maxleafPath(temp);
				}
				else
				{
					print("\n Two leaf nodes are not exist \n");
				}
			}
		}
	}
	//Display pre order elements
	fun preorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			//Print node value
			print("  " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Define trees
	var tree1: BinaryTree = BinaryTree();
	var tree2: BinaryTree = BinaryTree();
	var tree3: BinaryTree = BinaryTree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	           / \
	          1  -2  
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree1.root = TreeNode(1);
	tree1.root?.left = TreeNode(2);
	tree1.root?.right = TreeNode(3);
	tree1.root?.left?.left = TreeNode(3);
	tree1.root?.left?.right = TreeNode(4);
	tree1.root?.left?.right?.left = TreeNode(-7);
	tree1.root?.right?.left = TreeNode(6);
	tree1.root?.right?.right = TreeNode(5);
	tree1.root?.right?.left?.right = TreeNode(4);
	tree1.root?.right?.right?.right = TreeNode(2);
	tree1.root?.right?.left?.right?.left = TreeNode(1);
	tree1.root?.right?.left?.right?.right = TreeNode(-2);
	tree1.preorder(tree1.root);
	tree1.maxleafPath(tree1.root);
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    4   5 8   7
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree2.root = TreeNode(1);
	tree2.root?.left = TreeNode(2);
	tree2.root?.left?.left = TreeNode(4);
	tree2.root?.left?.right = TreeNode(5);
	tree2.root?.right = TreeNode(3);
	tree2.root?.right?.left = TreeNode(8);
	tree2.root?.right?.right = TreeNode(7);
	tree2.preorder(tree2.root);
	tree2.maxleafPath(tree2.root);
	/*
	        1
	       /   
	      2     
	     / 
	    4   
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree3.root = TreeNode(1);
	tree3.root?.left = TreeNode(2);
	tree3.root?.left?.left = TreeNode(3);
	tree3.preorder(tree3.root);
	tree3.maxleafPath(tree3.root);
}

Output

  1  2  3  4  -7  3  6  4  1  -2  5  2
 Result : 21
  1  2  4  5  3  8  7
 Result : 19
  1  2  3
 Two leaf nodes are not exist




Comment

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