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
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