Print the longest leaf to leaf path in a binary tree
The problem at hand deals with finding and printing the longest leaf-to-leaf path in a binary tree. In a binary tree, a leaf-to-leaf path is a path that starts from a leaf node, traverses through internal nodes, and ends at another leaf node. The goal is to identify the longest such path and print the sequence of nodes that constitute it.
Problem Statement
Given a binary tree, the task is to find the longest path between any two leaf nodes and print the nodes in that path.
Example
Consider the following binary tree:
4
/ \
-4 7
/ \ \
2 3 12
/ \ /
10 8 5
/ \
9 15
In this example, the longest leaf-to-leaf path is [9 10 3 -4 4 7 12 5 15]. Thus, the goal is to print this
path.
Idea to Solve
The problem can be solved using a recursive approach. We need to calculate the height of each internal node in the binary tree while keeping track of their respective parent nodes. Once we have the height of all internal nodes, we can traverse through them and find the pair of nodes whose sum of heights is the maximum. The parent node of this pair will be the root of the longest leaf-to-leaf path.
After identifying the parent node, we can recursively find the paths from the parent node to both of its child leaf nodes. Finally, we print these two paths, one from bottom to top for the left child and one from top to bottom for the right child.
Algorithm
-
Define a class
TreeNodeto represent a node in the binary tree. Each node will have adatavalue, a reference to its left child, and a reference to its right child. -
Define a class
InternalNodeHeightto store the height of internal nodes along with their parent nodes. -
Create a
BinaryTreeclass with methods:fingHeight(TreeNode node, HashMap<Integer, InternalNodeHeight> record): Calculate and record the height of each internal node using recursion.pathBottomToTop(ArrayList<Integer> path): Print the given path from bottom to top.pathTopToBottom(ArrayList<Integer> path): Print the given path from top to bottom.findPath(TreeNode node, int height, ArrayList<Integer> path): Recursively find the leaf-to-leaf path from a given node.longestLeafToLeaf(): Calculate the longest leaf-to-leaf path and print it.
-
In the
mainmethod:- Create a binary tree instance.
- Construct the binary tree by adding nodes and connecting them.
- Call the
longestLeafToLeafmethod to find and print the longest leaf-to-leaf path.
Program Solution
import java.util.HashMap;
import java.util.ArrayList;
/*
Java Program
Print the longest leaf to leaf path in a binary tree
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class InternalNodeHeight
{
public int left;
public int right;
public TreeNode parent;
public InternalNodeHeight(int left, int right, TreeNode parent)
{
// height of left subtree
this.left = left;
// height of right subtree
this.right = right;
// root of left and right subtree
this.parent = parent;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
// Finding height of all internal nodes in binary tree using recursion
public int fingHeight(TreeNode node, HashMap < Integer,
InternalNodeHeight > record)
{
if (node == null)
{
return 0;
}
else if (node.left == null && node.right == null)
{
// When node is leaf node
return 1;
}
// Height of left subtree
int l = fingHeight(node.left, record);
// Height of right subtree
int r = fingHeight(node.right, record);
if (node.left != null && node.right != null)
{
// Store height of internal node when not exist
if (!record.containsKey(l + r))
{
// Add new internal node height
InternalNodeHeight height = new InternalNodeHeight(l, r, node);
record.put(l + r, height);
}
}
if (l > r)
{
return l + 1;
}
else
{
return r + 1;
}
}
// Display given path from bottom to top direction
public void pathBottomToTop(ArrayList < Integer > path)
{
int i = path.size() - 1;
// print path
while (i >= 0)
{
System.out.print(" " + path.get(i));
i--;
}
}
// Display given path from top to bottom direction
public void pathTopToBottom(ArrayList < Integer > path)
{
int i = 0;
// print path
while (i < path.size())
{
System.out.print(" " + path.get(i));
i++;
}
}
// Find the first longest leaf path of which is exist in given node
public boolean findPath(TreeNode node, int height,
ArrayList < Integer > path)
{
if (node == null)
{
return false;
}
// Add path element
path.add(node.data);
if (height == 0)
{
if (node.left == null && node.right == null)
{
// Getting the path of first leaf node in given height
return true;
}
return false;
}
else if (findPath(node.left, height - 1, path)
|| findPath(node.right, height - 1, path))
{
// When path found
return true;
}
// Remove last path node
path.remove(path.size() - 1);
return false;
}
// Handles the request of finding longest leaf to leaf path in tree
public void longestLeafToLeaf()
{
// Use to collect height of internal node
HashMap < Integer, InternalNodeHeight > record =
new HashMap < Integer, InternalNodeHeight > ();
// This is use to collect leaf node path
ArrayList < Integer > path = new ArrayList < Integer > ();
// Calculate height of internal node
fingHeight(this.root, record);
int height = 0;
InternalNodeHeight auxiliary = null;
// Find a node which are longest path two leaf nodes
for (int key: record.keySet())
{
if (key > height)
{
height = key;
// Get the resultant parent node
auxiliary = record.get(key);
}
}
if (height == 0 || auxiliary == null)
{
// When no more than one leaf nodes
return;
}
else
{
// Find first leaf node path
findPath(auxiliary.parent.left, auxiliary.left - 1, path);
// Print first leaf node path
pathBottomToTop(path);
// Print ancestor node value
System.out.print(" " + auxiliary.parent.data);
path.clear();
// Find Second leaf node path
findPath(auxiliary.parent.right, auxiliary.right - 1, path);
// Print Second leaf node path
pathTopToBottom(path);
System.out.print("\n");
}
}
public static void main(String[] args)
{
// Create new binary tree
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 3 12
/ \ /
10 8 5
/ \
9 15
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode(4);
tree1.root.left = new TreeNode(-4);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.right.left = new TreeNode(10);
tree1.root.left.right.left.left = new TreeNode(9);
tree1.root.left.right.right = new TreeNode(8);
tree1.root.left.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(12);
tree1.root.right.right.left = new TreeNode(5);
tree1.root.right.right.left.right = new TreeNode(15);
// Case 1
tree1.longestLeafToLeaf();
/*
4
/ \
-4 7
/ \
2 3
/ \
10 8
/ \
9 1
/ \
6 5
-----------------
Constructing binary tree 2
*/
tree2.root = new TreeNode(4);
tree2.root.left = new TreeNode(-4);
tree2.root.left.right = new TreeNode(3);
tree2.root.left.right.left = new TreeNode(10);
tree2.root.left.right.left.left = new TreeNode(9);
tree2.root.left.right.left.left.left = new TreeNode(6);
tree2.root.left.right.right = new TreeNode(8);
tree2.root.left.right.right.right = new TreeNode(1);
tree2.root.left.right.right.right.right = new TreeNode(5);
tree2.root.left.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
// Case 2
tree2.longestLeafToLeaf();
}
}input
9 10 3 -4 4 7 12 5 15
6 9 10 3 8 1 5// Include header file
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
/*
C++ Program
Print the longest leaf to leaf path in a binary tree
*/
// Binary Tree node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class InternalNodeHeight
{
public: int left;
int right;
TreeNode *parent;
InternalNodeHeight(int left, int right, TreeNode *parent)
{
// height of left subtree
this->left = left;
// height of right subtree
this->right = right;
// root of left and right subtree
this->parent = parent;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
// Finding height of all internal nodes in binary tree using recursion
int fingHeight(TreeNode *node,
unordered_map < int, InternalNodeHeight* > &record)
{
if (node == NULL)
{
return 0;
}
else if (node->left == NULL && node->right == NULL)
{
// When node is leaf node
return 1;
}
// Height of left subtree
int l = this->fingHeight(node->left, record);
// Height of right subtree
int r = this->fingHeight(node->right, record);
if (node->left != NULL && node->right != NULL)
{
// Store height of internal node when not exist
if (record.find(l + r) == record.end())
{
// Add new internal node height
InternalNodeHeight *height = new InternalNodeHeight(l, r, node);
record[l + r] = height;
}
}
if (l > r)
{
return l + 1;
}
else
{
return r + 1;
}
}
// Display given path from bottom to top direction
void pathBottomToTop(vector < int > path)
{
int i = path.size() - 1;
// print path
while (i >= 0)
{
cout << " " << path.at(i);
i--;
}
}
// Display given path from top to bottom direction
void pathTopToBottom(vector < int > path)
{
int i = 0;
// print path
while (i < path.size())
{
cout << " " << path.at(i);
i++;
}
}
// Find the first longest leaf path of which is exist in given node
bool findPath(TreeNode *node, int height, vector < int > &path)
{
if (node == NULL)
{
return false;
}
// Add path element
path.push_back(node->data);
if (height == 0)
{
if (node->left == NULL && node->right == NULL)
{
// Getting the path of first leaf node in given height
return true;
}
return false;
}
else if (this->findPath(node->left, height - 1, path)
|| this->findPath(node->right, height - 1, path))
{
// When path found
return true;
}
// Remove last path node
path.erase(path.begin() + path.size() - 1);
return false;
}
// Handles the request of finding longest leaf to leaf path in tree
void longestLeafToLeaf()
{
// Use to collect height of internal node
unordered_map < int, InternalNodeHeight* > record;
// This is use to collect leaf node path
vector < int > path;
// Calculate height of internal node
this->fingHeight(this->root, record);
int height = 0;
InternalNodeHeight *auxiliary = NULL;
// Find a node which are longest path two leaf nodes
for (auto &info: record)
{
if (info.first > height)
{
height = info.first;
// Get the resultant parent node
auxiliary = record[info.first];
}
}
if (height == 0 || auxiliary == NULL)
{
// When, no more than one leaf nodes
return;
}
else
{
// Find first leaf node path
this->findPath(auxiliary->parent->left,
auxiliary->left - 1, path);
// Print first leaf node path
this->pathBottomToTop(path);
// Print ancestor node value
cout << " " << auxiliary->parent->data;
path.clear();
// Find Second leaf node path
this->findPath(auxiliary->parent->right,
auxiliary->right - 1, path);
// Print Second leaf node path
this->pathTopToBottom(path);
cout << "\n";
}
}
};
int main()
{
// Create new binary tree
BinaryTree *tree1 = new BinaryTree();
BinaryTree *tree2 = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 3 12
/ \ /
10 8 5
/ \
9 15
-----------------
Constructing binary tree
*/
tree1->root = new TreeNode(4);
tree1->root->left = new TreeNode(-4);
tree1->root->left->right = new TreeNode(3);
tree1->root->left->right->left = new TreeNode(10);
tree1->root->left->right->left->left = new TreeNode(9);
tree1->root->left->right->right = new TreeNode(8);
tree1->root->left->left = new TreeNode(2);
tree1->root->right = new TreeNode(7);
tree1->root->right->right = new TreeNode(12);
tree1->root->right->right->left = new TreeNode(5);
tree1->root->right->right->left->right = new TreeNode(15);
// Case 1
tree1->longestLeafToLeaf();
/*
4
/ \
-4 7
/ \
2 3
/ \
10 8
/ \
9 1
/ \
6 5
-----------------
Constructing binary tree 2
*/
tree2->root = new TreeNode(4);
tree2->root->left = new TreeNode(-4);
tree2->root->left->right = new TreeNode(3);
tree2->root->left->right->left = new TreeNode(10);
tree2->root->left->right->left->left = new TreeNode(9);
tree2->root->left->right->left->left->left = new TreeNode(6);
tree2->root->left->right->right = new TreeNode(8);
tree2->root->left->right->right->right = new TreeNode(1);
tree2->root->left->right->right->right->right = new TreeNode(5);
tree2->root->left->left = new TreeNode(2);
tree2->root->right = new TreeNode(7);
// Case 2
tree2->longestLeafToLeaf();
return 0;
}input
9 10 3 -4 4 7 12 5 15
6 9 10 3 8 1 5// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program
Print the longest leaf to leaf path in a binary tree
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class InternalNodeHeight
{
public int left;
public int right;
public TreeNode parent;
public InternalNodeHeight(int left, int right, TreeNode parent)
{
// height of left subtree
this.left = left;
// height of right subtree
this.right = right;
// root of left and right subtree
this.parent = parent;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
// Finding height of all internal nodes in binary tree using recursion
public int fingHeight(TreeNode node, Dictionary < int, InternalNodeHeight > record)
{
if (node == null)
{
return 0;
}
else if (node.left == null && node.right == null)
{
// When node is leaf node
return 1;
}
// Height of left subtree
int l = this.fingHeight(node.left, record);
// Height of right subtree
int r = this.fingHeight(node.right, record);
if (node.left != null && node.right != null)
{
// Store height of internal node when not exist
if (!record.ContainsKey(l + r))
{
// Add new internal node height
InternalNodeHeight height = new InternalNodeHeight(l, r, node);
record.Add(l + r, height);
}
}
if (l > r)
{
return l + 1;
}
else
{
return r + 1;
}
}
// Display given path from bottom to top direction
public void pathBottomToTop(List < int > path)
{
int i = path.Count - 1;
// print path
while (i >= 0)
{
Console.Write(" " + path[i]);
i--;
}
}
// Display given path from top to bottom direction
public void pathTopToBottom(List < int > path)
{
int i = 0;
// print path
while (i < path.Count)
{
Console.Write(" " + path[i]);
i++;
}
}
// Find the first longest leaf path of which is exist in given node
public Boolean findPath(TreeNode node, int height, List < int > path)
{
if (node == null)
{
return false;
}
// Add path element
path.Add(node.data);
if (height == 0)
{
if (node.left == null && node.right == null)
{
// Getting the path of first leaf node in given height
return true;
}
return false;
}
else if (this.findPath(node.left, height - 1, path) || this.findPath(node.right, height - 1, path))
{
// When path found
return true;
}
// Remove last path node
path.RemoveAt(path.Count - 1);
return false;
}
// Handles the request of finding longest leaf to leaf path in tree
public void longestLeafToLeaf()
{
// Use to collect height of internal node
Dictionary < int, InternalNodeHeight > record =
new Dictionary < int, InternalNodeHeight > ();
// This is use to collect leaf node path
List < int > path = new List < int > ();
// Calculate height of internal node
this.fingHeight(this.root, record);
int height = 0;
InternalNodeHeight auxiliary = null;
// Find a node which are longest path two leaf nodes
foreach(KeyValuePair < int, InternalNodeHeight > info in record)
{
if (info.Key > height)
{
height = info.Key;
// Get the resultant parent node
auxiliary = info.Value;
}
}
if (height == 0 || auxiliary == null)
{
// When no more than one leaf nodes
return;
}
else
{
// Find first leaf node path
this.findPath(auxiliary.parent.left, auxiliary.left - 1, path);
// Print first leaf node path
this.pathBottomToTop(path);
// Print ancestor node value
Console.Write(" " + auxiliary.parent.data);
path.Clear();
// Find Second leaf node path
this.findPath(auxiliary.parent.right, auxiliary.right - 1, path);
// Print Second leaf node path
this.pathTopToBottom(path);
Console.Write("\n");
}
}
public static void Main(String[] args)
{
// Create new binary tree
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 3 12
/ \ /
10 8 5
/ \
9 15
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode(4);
tree1.root.left = new TreeNode(-4);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.right.left = new TreeNode(10);
tree1.root.left.right.left.left = new TreeNode(9);
tree1.root.left.right.right = new TreeNode(8);
tree1.root.left.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(12);
tree1.root.right.right.left = new TreeNode(5);
tree1.root.right.right.left.right = new TreeNode(15);
// Case 1
tree1.longestLeafToLeaf();
/*
4
/ \
-4 7
/ \
2 3
/ \
10 8
/ \
9 1
/ \
6 5
-----------------
Constructing binary tree 2
*/
tree2.root = new TreeNode(4);
tree2.root.left = new TreeNode(-4);
tree2.root.left.right = new TreeNode(3);
tree2.root.left.right.left = new TreeNode(10);
tree2.root.left.right.left.left = new TreeNode(9);
tree2.root.left.right.left.left.left = new TreeNode(6);
tree2.root.left.right.right = new TreeNode(8);
tree2.root.left.right.right.right = new TreeNode(1);
tree2.root.left.right.right.right.right = new TreeNode(5);
tree2.root.left.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
// Case 2
tree2.longestLeafToLeaf();
}
}input
9 10 3 -4 4 7 12 5 15
6 9 10 3 8 1 5<?php
/*
Php Program
Print the longest leaf to leaf path in a binary tree
*/
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
public function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class InternalNodeHeight
{
public $left;
public $right;
public $parent;
public function __construct($left, $right, $parent)
{
// height of left subtree
$this->left = $left;
// height of right subtree
$this->right = $right;
// root of left and right subtree
$this->parent = $parent;
}
}
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
// Finding height of all internal nodes in binary tree using recursion
public function fingHeight($node, &$record)
{
if ($node == NULL)
{
return 0;
}
else if ($node->left == NULL && $node->right == NULL)
{
// When node is leaf node
return 1;
}
// Height of left subtree
$l = $this->fingHeight($node->left, $record);
// Height of right subtree
$r = $this->fingHeight($node->right, $record);
if ($node->left != NULL && $node->right != NULL)
{
// Store height of internal node when not exist
if (!array_key_exists($l + $r, $record))
{
// Add new internal node height
$height = new InternalNodeHeight($l, $r, $node);
$record[$l + $r] = $height;
}
}
if ($l > $r)
{
return $l + 1;
}
else
{
return $r + 1;
}
}
// Display given path from bottom to top direction
public function pathBottomToTop($path)
{
$i = count($path) - 1;
// print path
while ($i >= 0)
{
echo(" ".$path[$i]);
$i--;
}
}
// Display given path from top to bottom direction
public function pathTopToBottom($path)
{
$i = 0;
// print path
while ($i < count($path))
{
echo(" ".$path[$i]);
$i++;
}
}
// Find the first longest leaf path of which is exist in given node
public function findPath($node, $height, &$path)
{
if ($node == NULL)
{
return false;
}
// Add path element
$path[] = $node->data;
if ($height == 0)
{
if ($node->left == NULL && $node->right == NULL)
{
// Getting the path of first leaf node in given height
return true;
}
return false;
}
else if ($this->findPath($node->left, $height - 1, $path)
|| $this->findPath($node->right, $height - 1, $path))
{
// When path found
return true;
}
// Remove last path node
array_pop($path);
return false;
}
// Handles the request of finding longest leaf to leaf path in tree
public function longestLeafToLeaf()
{
// Use to collect height of internal node
$record = array();
// This is use to collect leaf node path
$path = array();
// Calculate height of internal node
$this->fingHeight($this->root, $record);
$height = 0;
$auxiliary = NULL;
// Find a node which are longest path two leaf nodes
foreach($record as $key => $value)
{
if ($key > $height)
{
$height = $key;
// Get the resultant parent node
$auxiliary = $value;
}
}
if ($height == 0 || $auxiliary == NULL)
{
// When no more than one leaf nodes
return;
}
else
{
// Find first leaf node path
$this->findPath($auxiliary->parent->left,
$auxiliary->left - 1, $path);
// Print first leaf node path
$this->pathBottomToTop($path);
// Print ancestor node value
echo(" ".$auxiliary->parent->data);
$path = array();
// Find Second leaf node path
$this->findPath($auxiliary->parent->right,
$auxiliary->right - 1, $path);
// Print Second leaf node path
$this->pathTopToBottom($path);
echo("\n");
}
}
}
function main()
{
// Create new binary tree
$tree1 = new BinaryTree();
$tree2 = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 3 12
/ \ /
10 8 5
/ \
9 15
-----------------
Constructing binary tree
*/
$tree1->root = new TreeNode(4);
$tree1->root->left = new TreeNode(-4);
$tree1->root->left->right = new TreeNode(3);
$tree1->root->left->right->left = new TreeNode(10);
$tree1->root->left->right->left->left = new TreeNode(9);
$tree1->root->left->right->right = new TreeNode(8);
$tree1->root->left->left = new TreeNode(2);
$tree1->root->right = new TreeNode(7);
$tree1->root->right->right = new TreeNode(12);
$tree1->root->right->right->left = new TreeNode(5);
$tree1->root->right->right->left->right = new TreeNode(15);
// Case 1
$tree1->longestLeafToLeaf();
/*
4
/ \
-4 7
/ \
2 3
/ \
10 8
/ \
9 1
/ \
6 5
-----------------
Constructing binary tree 2
*/
$tree2->root = new TreeNode(4);
$tree2->root->left = new TreeNode(-4);
$tree2->root->left->right = new TreeNode(3);
$tree2->root->left->right->left = new TreeNode(10);
$tree2->root->left->right->left->left = new TreeNode(9);
$tree2->root->left->right->left->left->left = new TreeNode(6);
$tree2->root->left->right->right = new TreeNode(8);
$tree2->root->left->right->right->right = new TreeNode(1);
$tree2->root->left->right->right->right->right = new TreeNode(5);
$tree2->root->left->left = new TreeNode(2);
$tree2->root->right = new TreeNode(7);
// Case 2
$tree2->longestLeafToLeaf();
}
main();input
9 10 3 -4 4 7 12 5 15
6 9 10 3 8 1 5/*
Node JS Program
Print the longest leaf to leaf path in a binary tree
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class InternalNodeHeight
{
constructor(left, right, parent)
{
// height of left subtree
this.left = left;
// height of right subtree
this.right = right;
// root of left and right subtree
this.parent = parent;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
// Finding height of all internal nodes in binary tree using recursion
fingHeight(node, record)
{
if (node == null)
{
return 0;
}
else if (node.left == null && node.right == null)
{
// When node is leaf node
return 1;
}
// Height of left subtree
var l = this.fingHeight(node.left, record);
// Height of right subtree
var r = this.fingHeight(node.right, record);
if (node.left != null && node.right != null)
{
// Store height of internal node when not exist
if (!record.has(l + r))
{
// Add new internal node height
var height = new InternalNodeHeight(l, r, node);
record.set(l + r, height);
}
}
if (l > r)
{
return l + 1;
}
else
{
return r + 1;
}
}
// Display given path from bottom to top direction
pathBottomToTop(path)
{
var i = path.length - 1;
// print path
while (i >= 0)
{
process.stdout.write(" " + path[i]);
i--;
}
}
// Display given path from top to bottom direction
pathTopToBottom(path)
{
var i = 0;
// print path
while (i < path.length)
{
process.stdout.write(" " + path[i]);
i++;
}
}
// Find the first longest leaf path of which is exist in given node
findPath(node, height, path)
{
if (node == null)
{
return false;
}
// Add path element
path.push(node.data);
if (height == 0)
{
if (node.left == null && node.right == null)
{
// Getting the path of first leaf node in given height
return true;
}
return false;
}
else if (this.findPath(node.left, height - 1, path)
|| this.findPath(node.right, height - 1, path))
{
// When path found
return true;
}
// Remove last path node
path.pop();
return false;
}
// Handles the request of finding longest leaf to leaf path in tree
longestLeafToLeaf()
{
// Use to collect height of internal node
var record = new Map();
// This is use to collect leaf node path
var path = [];
// Calculate height of internal node
this.fingHeight(this.root, record);
var height = 0;
var auxiliary = null;
// Find a node which are longest path two leaf nodes
for(let [key, value] of record)
{
if (key > height)
{
height = key;
// Get the resultant parent node
auxiliary = value;
}
}
if (height == 0 || auxiliary == null)
{
// When no more than one leaf nodes
return;
}
else
{
// Find first leaf node path
this.findPath(auxiliary.parent.left,
auxiliary.left - 1, path);
// Print first leaf node path
this.pathBottomToTop(path);
// Print ancestor node value
process.stdout.write(" " + auxiliary.parent.data);
path = [];
// Find Second leaf node path
this.findPath(auxiliary.parent.right,
auxiliary.right - 1, path);
// Print Second leaf node path
this.pathTopToBottom(path);
process.stdout.write("\n");
}
}
}
function main()
{
// Create new binary tree
var tree1 = new BinaryTree();
var tree2 = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 3 12
/ \ /
10 8 5
/ \
9 15
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode(4);
tree1.root.left = new TreeNode(-4);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.right.left = new TreeNode(10);
tree1.root.left.right.left.left = new TreeNode(9);
tree1.root.left.right.right = new TreeNode(8);
tree1.root.left.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(12);
tree1.root.right.right.left = new TreeNode(5);
tree1.root.right.right.left.right = new TreeNode(15);
// Case 1
tree1.longestLeafToLeaf();
/*
4
/ \
-4 7
/ \
2 3
/ \
10 8
/ \
9 1
/ \
6 5
-----------------
Constructing binary tree 2
*/
tree2.root = new TreeNode(4);
tree2.root.left = new TreeNode(-4);
tree2.root.left.right = new TreeNode(3);
tree2.root.left.right.left = new TreeNode(10);
tree2.root.left.right.left.left = new TreeNode(9);
tree2.root.left.right.left.left.left = new TreeNode(6);
tree2.root.left.right.right = new TreeNode(8);
tree2.root.left.right.right.right = new TreeNode(1);
tree2.root.left.right.right.right.right = new TreeNode(5);
tree2.root.left.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
// Case 2
tree2.longestLeafToLeaf();
}
main();input
9 10 3 -4 4 7 12 5 15
6 9 10 3 8 1 5# Python 3 Program
# Print the longest leaf to leaf path in a binary tree
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
class InternalNodeHeight :
def __init__(self, left, right, parent) :
# height of left subtree
self.left = left
# height of right subtree
self.right = right
# root of left and right subtree
self.parent = parent
class BinaryTree :
def __init__(self) :
self.root = None
# Finding height of all internal nodes in binary tree using recursion
def fingHeight(self, node, record) :
if (node == None) :
return 0
elif (node.left == None and node.right == None) :
# When node is leaf node
return 1
# Height of left subtree
l = self.fingHeight(node.left, record)
# Height of right subtree
r = self.fingHeight(node.right, record)
if (node.left != None and node.right != None) :
# Store height of internal node when not exist
if (not l + r in record.keys()) :
# Add new internal node height
height = InternalNodeHeight(l, r, node)
record[l + r] = height
if (l > r) :
return l + 1
else :
return r + 1
# Display given path from bottom to top direction
def pathBottomToTop(self, path) :
i = len(path) - 1
# print path
while (i >= 0) :
print(" ", path[i], end = "")
i -= 1
# Display given path from top to bottom direction
def pathTopToBottom(self, path) :
i = 0
# print path
while (i < len(path)) :
print(" ", path[i], end = "")
i += 1
# Find the first longest leaf path of which is exist in given node
def findPath(self, node, height, path) :
if (node == None) :
return False
# Add path element
path.append(node.data)
if (height == 0) :
if (node.left == None and node.right == None) :
# Getting the path of first leaf node in given height
return True
return False
elif (self.findPath(node.left, height - 1, path) or
self.findPath(node.right, height - 1, path)) :
# When path found
return True
# Remove last path node
path.pop()
return False
# Handles the request of finding longest leaf to leaf path in tree
def longestLeafToLeaf(self) :
# Use to collect height of internal node
record = dict()
# This is use to collect leaf node path
path = []
# Calculate height of internal node
self.fingHeight(self.root, record)
height = 0
auxiliary = None
# Find a node which are longest path two leaf nodes
for key, value in record.items() :
if (key > height) :
height = key
# Get the resultant parent node
auxiliary = value
if (height == 0 or auxiliary == None) :
# When no more than one leaf nodes
return
else :
# Find first leaf node path
self.findPath(auxiliary.parent.left, auxiliary.left - 1, path)
# Print first leaf node path
self.pathBottomToTop(path)
# Print ancestor node value
print(" ", auxiliary.parent.data, end = "")
path.clear()
# Find Second leaf node path
self.findPath(auxiliary.parent.right, auxiliary.right - 1, path)
# Print Second leaf node path
self.pathTopToBottom(path)
print(end = "\n")
def main() :
# Create new binary tree
tree1 = BinaryTree()
tree2 = BinaryTree()
# 4
# / \
# -4 7
# / \ \
# 2 3 12
# / \ /
# 10 8 5
# / \
# 9 15
# -----------------
# Constructing binary tree
tree1.root = TreeNode(4)
tree1.root.left = TreeNode(-4)
tree1.root.left.right = TreeNode(3)
tree1.root.left.right.left = TreeNode(10)
tree1.root.left.right.left.left = TreeNode(9)
tree1.root.left.right.right = TreeNode(8)
tree1.root.left.left = TreeNode(2)
tree1.root.right = TreeNode(7)
tree1.root.right.right = TreeNode(12)
tree1.root.right.right.left = TreeNode(5)
tree1.root.right.right.left.right = TreeNode(15)
# Case 1
tree1.longestLeafToLeaf()
# 4
# / \
# -4 7
# / \
# 2 3
# / \
# 10 8
# / \
# 9 1
# / \
# 6 5
# -----------------
# Constructing binary tree 2
tree2.root = TreeNode(4)
tree2.root.left = TreeNode(-4)
tree2.root.left.right = TreeNode(3)
tree2.root.left.right.left = TreeNode(10)
tree2.root.left.right.left.left = TreeNode(9)
tree2.root.left.right.left.left.left = TreeNode(6)
tree2.root.left.right.right = TreeNode(8)
tree2.root.left.right.right.right = TreeNode(1)
tree2.root.left.right.right.right.right = TreeNode(5)
tree2.root.left.left = TreeNode(2)
tree2.root.right = TreeNode(7)
# Case 2
tree2.longestLeafToLeaf()
if __name__ == "__main__": main()input
9 10 3 -4 4 7 12 5 15
6 9 10 3 8 1 5# Ruby Program
# Print the longest leaf to leaf path in a binary tree
# Binary 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)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
class InternalNodeHeight
# Define the accessor and reader of class InternalNodeHeight
attr_reader :left, :right, :parent
attr_accessor :left, :right, :parent
def initialize(left, right, parent)
# height of left subtree
self.left = left
# height of right subtree
self.right = right
# root of left and right subtree
self.parent = parent
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
# Finding height of all internal nodes in binary tree using recursion
def fingHeight(node, record)
if (node == nil)
return 0
elsif(node.left == nil && node.right == nil)
# When node is leaf node
return 1
end
# Height of left subtree
l = self.fingHeight(node.left, record)
# Height of right subtree
r = self.fingHeight(node.right, record)
if (node.left != nil && node.right != nil)
# Store height of internal node when not exist
if (! record.key?(l + r))
# Add new internal node height
height = InternalNodeHeight.new(l, r, node)
record[l + r] = height
end
end
if (l > r)
return l + 1
else
return r + 1
end
end
# Display given path from bottom to top direction
def pathBottomToTop(path)
i = path.length - 1
# print path
while (i >= 0)
print(" ", path[i])
i -= 1
end
end
# Display given path from top to bottom direction
def pathTopToBottom(path)
i = 0
# print path
while (i < path.length)
print(" ", path[i])
i += 1
end
end
# Find the first longest leaf path of which is exist in given node
def findPath(node, height, path)
if (node == nil)
return false
end
# Add path element
path.push(node.data)
if (height == 0)
if (node.left == nil && node.right == nil)
# Getting the path of first leaf node in given height
return true
end
return false
elsif(self.findPath(node.left, height - 1, path) ||
self.findPath(node.right, height - 1, path))
# When path found
return true
end
# Remove last path node
path.pop()
return false
end
# Handles the request of finding longest leaf to leaf path in tree
def longestLeafToLeaf()
# Use to collect height of internal node
record = Hash.new()
# This is use to collect leaf node path
path = []
# Calculate height of internal node
self.fingHeight(self.root, record)
height = 0
auxiliary = nil
# Find a node which are longest path two leaf nodes
record.each {
| key, value |
if (key > height)
height = key
# Get the resultant parent node
auxiliary = value
end
}
if (height == 0 || auxiliary == nil)
# When no more than one leaf nodes
return
else
# Find first leaf node path
self.findPath(auxiliary.parent.left, auxiliary.left - 1, path)
# Print first leaf node path
self.pathBottomToTop(path)
# Print ancestor node value
print(" ", auxiliary.parent.data)
path.clear()
# Find Second leaf node path
self.findPath(auxiliary.parent.right, auxiliary.right - 1, path)
# Print Second leaf node path
self.pathTopToBottom(path)
print("\n")
end
end
end
def main()
# Create new binary tree
tree1 = BinaryTree.new()
tree2 = BinaryTree.new()
# 4
# / \
# -4 7
# / \ \
# 2 3 12
# / \ /
# 10 8 5
# / \
# 9 15
# -----------------
# Constructing binary tree
tree1.root = TreeNode.new(4)
tree1.root.left = TreeNode.new(-4)
tree1.root.left.right = TreeNode.new(3)
tree1.root.left.right.left = TreeNode.new(10)
tree1.root.left.right.left.left = TreeNode.new(9)
tree1.root.left.right.right = TreeNode.new(8)
tree1.root.left.left = TreeNode.new(2)
tree1.root.right = TreeNode.new(7)
tree1.root.right.right = TreeNode.new(12)
tree1.root.right.right.left = TreeNode.new(5)
tree1.root.right.right.left.right = TreeNode.new(15)
# Case 1
tree1.longestLeafToLeaf()
# 4
# / \
# -4 7
# / \
# 2 3
# / \
# 10 8
# / \
# 9 1
# / \
# 6 5
# -----------------
# Constructing binary tree 2
tree2.root = TreeNode.new(4)
tree2.root.left = TreeNode.new(-4)
tree2.root.left.right = TreeNode.new(3)
tree2.root.left.right.left = TreeNode.new(10)
tree2.root.left.right.left.left = TreeNode.new(9)
tree2.root.left.right.left.left.left = TreeNode.new(6)
tree2.root.left.right.right = TreeNode.new(8)
tree2.root.left.right.right.right = TreeNode.new(1)
tree2.root.left.right.right.right.right = TreeNode.new(5)
tree2.root.left.left = TreeNode.new(2)
tree2.root.right = TreeNode.new(7)
# Case 2
tree2.longestLeafToLeaf()
end
main()input
9 10 3 -4 4 7 12 5 15
6 9 10 3 8 1 5
import scala.collection.mutable._;
/*
Scala Program
Print the longest leaf to leaf path in a binary tree
*/
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data,null,null);
}
}
class InternalNodeHeight(var left: Int,
var right: Int,
var parent: TreeNode);
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Finding height of all internal nodes in binary tree using recursion
def fingHeight(node: TreeNode, record: HashMap[Int, InternalNodeHeight]): Int = {
if (node == null)
{
return 0;
}
else if (node.left == null && node.right == null)
{
// When node is leaf node
return 1;
}
// Height of left subtree
var l: Int = fingHeight(node.left, record);
// Height of right subtree
var r: Int = fingHeight(node.right, record);
if (node.left != null && node.right != null)
{
// Store height of internal node when not exist
if (!record.contains(l + r))
{
// Add new internal node height
var height: InternalNodeHeight = new InternalNodeHeight(l, r, node);
record.addOne(l + r, height);
}
}
if (l > r)
{
return l + 1;
}
else
{
return r + 1;
}
}
// Display given path from bottom to top direction
def pathBottomToTop(path: ArrayBuffer[Int]): Unit = {
var i: Int = path.size - 1;
// print path
while (i >= 0)
{
print(" " + path(i));
i -= 1;
}
}
// Display given path from top to bottom direction
def pathTopToBottom(path: ArrayBuffer[Int]): Unit = {
var i: Int = 0;
// print path
while (i < path.size)
{
print(" " + path(i));
i += 1;
}
}
// Find the first longest leaf path of which is exist in given node
def findPath(node: TreeNode, height: Int, path: ArrayBuffer[Int]): Boolean = {
if (node == null)
{
return false;
}
// Add path element
path += node.data;
if (height == 0)
{
if (node.left == null && node.right == null)
{
// Getting the path of first leaf node in given height
return true;
}
return false;
}
else if (findPath(node.left, height - 1, path) || findPath(node.right, height - 1, path))
{
// When path found
return true;
}
// Remove last path node
path.remove(path.size - 1);
return false;
}
// Handles the request of finding longest leaf to leaf path in tree
def longestLeafToLeaf(): Unit = {
// Use to collect height of internal node
var record: HashMap[Int, InternalNodeHeight] = new HashMap[Int, InternalNodeHeight]();
// This is use to collect leaf node path
var path: ArrayBuffer[Int] = new ArrayBuffer[Int]();
// Calculate height of internal node
fingHeight(this.root, record);
var height: Int = 0;
var auxiliary: InternalNodeHeight = null;
// Find a node which are longest path two leaf nodes
for ((key, value) <- record)
{
if (key > height)
{
height = key;
// Get the resultant parent node
auxiliary = value;
}
}
if (height == 0 || auxiliary == null)
{
// When no more than one leaf nodes
return;
}
else
{
// Find first leaf node path
findPath(auxiliary.parent.left, auxiliary.left - 1, path);
// Print first leaf node path
pathBottomToTop(path);
// Print ancestor node value
print(" " + auxiliary.parent.data);
path.clear();
// Find Second leaf node path
findPath(auxiliary.parent.right, auxiliary.right - 1, path);
// Print Second leaf node path
pathTopToBottom(path);
print("\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create new binary tree
var tree1: BinaryTree = new BinaryTree();
var tree2: BinaryTree = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 3 12
/ \ /
10 8 5
/ \
9 15
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode(4);
tree1.root.left = new TreeNode(-4);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.right.left = new TreeNode(10);
tree1.root.left.right.left.left = new TreeNode(9);
tree1.root.left.right.right = new TreeNode(8);
tree1.root.left.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(12);
tree1.root.right.right.left = new TreeNode(5);
tree1.root.right.right.left.right = new TreeNode(15);
// Case 1
tree1.longestLeafToLeaf();
/*
4
/ \
-4 7
/ \
2 3
/ \
10 8
/ \
9 1
/ \
6 5
-----------------
Constructing binary tree 2
*/
tree2.root = new TreeNode(4);
tree2.root.left = new TreeNode(-4);
tree2.root.left.right = new TreeNode(3);
tree2.root.left.right.left = new TreeNode(10);
tree2.root.left.right.left.left = new TreeNode(9);
tree2.root.left.right.left.left.left = new TreeNode(6);
tree2.root.left.right.right = new TreeNode(8);
tree2.root.left.right.right.right = new TreeNode(1);
tree2.root.left.right.right.right.right = new TreeNode(5);
tree2.root.left.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
// Case 2
tree2.longestLeafToLeaf();
}
}input
9 10 3 -4 4 7 12 5 15
6 9 10 3 8 1 5/*
Swift 4 Program
Print the longest leaf to leaf path in a binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class InternalNodeHeight
{
var left: Int;
var right: Int;
var parent: TreeNode? ;
init(_ left: Int, _ right: Int, _ parent: TreeNode? )
{
// height of left subtree
self.left = left;
// height of right subtree
self.right = right;
// root of left and right subtree
self.parent = parent;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Finding height of all internal nodes in binary tree using recursion
func fingHeight(_ node: TreeNode? ,
_ record :inout[Int: InternalNodeHeight?] ) -> Int
{
if (node == nil)
{
return 0;
}
else if (node!.left == nil && node!.right == nil)
{
// When node is leaf node
return 1;
}
// Height of left subtree
let l: Int = self.fingHeight(node!.left, &record);
// Height of right subtree
let r: Int = self.fingHeight(node!.right, &record);
if (node!.left != nil && node!.right != nil)
{
// Store height of internal node when not exist
if (record.keys.contains(l + r) == false)
{
// Add new internal node height
let height: InternalNodeHeight? = InternalNodeHeight(l, r, node);
record[l + r] = height;
}
}
if (l > r)
{
return l + 1;
}
else
{
return r + 1;
}
}
// Display given path from bottom to top direction
func pathBottomToTop(_ path: [Int] )
{
var i: Int = path.count - 1;
// print path
while (i >= 0)
{
print(" ", path[i], terminator: "");
i -= 1;
}
}
// Display given path from top to bottom direction
func pathTopToBottom(_ path: [Int] )
{
var i: Int = 0;
// print path
while (i < path.count)
{
print(" ", path[i], terminator: "");
i += 1;
}
}
// Find the first longest leaf path of which is exist in given node
func findPath(_ node: TreeNode? , _ height : Int, _ path:inout [Int] ) -> Bool
{
if (node == nil)
{
return false;
}
// Add path element
path.append(node!.data);
if (height == 0)
{
if (node!.left == nil && node!.right == nil)
{
// Getting the path of first leaf node in given height
return true;
}
return false;
}
else if (self.findPath(node!.left, height - 1, &path)
|| self.findPath(node!.right, height - 1, &path))
{
// When path found
return true;
}
// Remove last path node
path.removeLast();
return false;
}
// Handles the request of finding longest leaf to leaf path in tree
func longestLeafToLeaf()
{
// Use to collect height of internal node
var record = [Int : InternalNodeHeight?]();
// This is use to collect leaf node path
var path = [Int]();
// Calculate height of internal node
let _ = self.fingHeight(self.root, &record);
var height: Int = 0;
var auxiliary: InternalNodeHeight? = nil;
// Find a node which are longest path two leaf nodes
for (key, value) in record
{
if (key > height)
{
height = key;
// Get the resultant parent node
auxiliary = value;
}
}
if (height == 0 || auxiliary == nil)
{
// When no more than one leaf nodes
return;
}
else
{
// Find first leaf node path
let _ = self.findPath(auxiliary!.parent!.left,
auxiliary!.left - 1, &path);
// Print first leaf node path
self.pathBottomToTop(path);
// Print ancestor node value
print(" ", auxiliary!.parent!.data, terminator: "");
path.removeAll();
// Find Second leaf node path
let _ = self.findPath(auxiliary!.parent!.right,
auxiliary!.right - 1, &path);
// Print Second leaf node path
self.pathTopToBottom(path);
print(terminator: "\n");
}
}
}
func main()
{
// Create new binary tree
let tree1: BinaryTree = BinaryTree();
let tree2: BinaryTree = BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 3 12
/ \ /
10 8 5
/ \
9 15
-----------------
Constructing binary tree
*/
tree1.root = TreeNode(4);
tree1.root!.left = TreeNode(-4);
tree1.root!.left!.right = TreeNode(3);
tree1.root!.left!.right!.left = TreeNode(10);
tree1.root!.left!.right!.left!.left = TreeNode(9);
tree1.root!.left!.right!.right = TreeNode(8);
tree1.root!.left!.left = TreeNode(2);
tree1.root!.right = TreeNode(7);
tree1.root!.right!.right = TreeNode(12);
tree1.root!.right!.right!.left = TreeNode(5);
tree1.root!.right!.right!.left!.right = TreeNode(15);
// Case 1
tree1.longestLeafToLeaf();
/*
4
/ \
-4 7
/ \
2 3
/ \
10 8
/ \
9 1
/ \
6 5
-----------------
Constructing binary tree 2
*/
tree2.root = TreeNode(4);
tree2.root!.left = TreeNode(-4);
tree2.root!.left!.right = TreeNode(3);
tree2.root!.left!.right!.left = TreeNode(10);
tree2.root!.left!.right!.left!.left = TreeNode(9);
tree2.root!.left!.right!.left!.left!.left = TreeNode(6);
tree2.root!.left!.right!.right = TreeNode(8);
tree2.root!.left!.right!.right!.right = TreeNode(1);
tree2.root!.left!.right!.right!.right!.right = TreeNode(5);
tree2.root!.left!.left = TreeNode(2);
tree2.root!.right = TreeNode(7);
// Case 2
tree2.longestLeafToLeaf();
}
main();input
9 10 3 -4 4 7 12 5 15
6 9 10 3 8 1 5/*
Kotlin Program
Print the longest leaf to leaf path in a binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class InternalNodeHeight
{
var left: Int;
var right: Int;
var parent: TreeNode ? ;
constructor(left: Int, right: Int, parent: TreeNode ? )
{
// height of left subtree
this.left = left;
// height of right subtree
this.right = right;
// root of left and right subtree
this.parent = parent;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// Finding height of all internal nodes in binary tree using recursion
fun fingHeight(node: TreeNode ? ,
record : MutableMap<Int, InternalNodeHeight>): Int
{
if (node == null)
{
return 0;
}
else if (node.left == null && node.right == null)
{
// When node is leaf node
return 1;
}
// Height of left subtree
val l: Int = this.fingHeight(node.left, record);
// Height of right subtree
val r: Int = this.fingHeight(node.right, record);
if (node.left != null && node.right != null)
{
// Store height of internal node when not exist
if (!record.containsKey(l + r))
{
// Add new internal node height
var height: InternalNodeHeight = InternalNodeHeight(l, r, node);
record.put(l + r, height);
}
}
if (l > r)
{
return l + 1;
}
else
{
return r + 1;
}
}
// Display given path from bottom to top direction
fun pathBottomToTop(path: MutableList<Int> ): Unit
{
var i: Int = path.size - 1;
// print path
while (i >= 0)
{
print(" " + path[i]);
i -= 1;
}
}
// Display given path from top to bottom direction
fun pathTopToBottom(path: MutableList<Int> ): Unit
{
var i: Int = 0;
// print path
while (i < path.size)
{
print(" " + path[i]);
i += 1;
}
}
// Find the first longest leaf path of which is exist in given node
fun findPath(node: TreeNode ? , height : Int,
path: MutableList<Int> ): Boolean
{
if (node == null)
{
return false;
}
// Add path element
path.add(node.data);
if (height == 0)
{
if (node.left == null && node.right == null)
{
// Getting the path of first leaf node in given height
return true;
}
return false;
}
else if (this.findPath(node.left, height - 1, path)
|| this.findPath(node.right, height - 1, path))
{
// When path found
return true;
}
// Remove last path node
path.removeAt(path.size - 1);
return false;
}
// Handles the request of finding longest leaf to leaf path in tree
fun longestLeafToLeaf(): Unit
{
// Use to collect height of internal node
var record = mutableMapOf < Int , InternalNodeHeight > ();
// This is use to collect leaf node path
var path = mutableListOf <Int> ();
// Calculate height of internal node
this.fingHeight(this.root, record);
var height: Int = 0;
var auxiliary: InternalNodeHeight? = null;
// Find a node which are longest path two leaf nodes
for ((key, value) in record)
{
if (key > height)
{
height = key;
// Get the resultant parent node
auxiliary = value;
}
}
if (height == 0 || auxiliary == null)
{
// When no more than one leaf nodes
return;
}
else
{
// Find first leaf node path
this.findPath(auxiliary.parent?.left, auxiliary.left - 1, path);
// Print first leaf node path
this.pathBottomToTop(path);
// Print ancestor node value
print(" " + auxiliary.parent?.data);
path.clear();
// Find Second leaf node path
this.findPath(auxiliary.parent?.right, auxiliary.right - 1, path);
// Print Second leaf node path
this.pathTopToBottom(path);
print("\n");
}
}
}
fun main(args: Array < String > ): Unit
{
// Create new binary tree
val tree1: BinaryTree = BinaryTree();
val tree2: BinaryTree = BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 3 12
/ \ /
10 8 5
/ \
9 15
-----------------
Constructing binary tree
*/
tree1.root = TreeNode(4);
tree1.root?.left = TreeNode(-4);
tree1.root?.left?.right = TreeNode(3);
tree1.root?.left?.right?.left = TreeNode(10);
tree1.root?.left?.right?.left?.left = TreeNode(9);
tree1.root?.left?.right?.right = TreeNode(8);
tree1.root?.left?.left = TreeNode(2);
tree1.root?.right = TreeNode(7);
tree1.root?.right?.right = TreeNode(12);
tree1.root?.right?.right?.left = TreeNode(5);
tree1.root?.right?.right?.left?.right = TreeNode(15);
// Case 1
tree1.longestLeafToLeaf();
/*
4
/ \
-4 7
/ \
2 3
/ \
10 8
/ \
9 1
/ \
6 5
-----------------
Constructing binary tree 2
*/
tree2.root = TreeNode(4);
tree2.root?.left = TreeNode(-4);
tree2.root?.left?.right = TreeNode(3);
tree2.root?.left?.right?.left = TreeNode(10);
tree2.root?.left?.right?.left?.left = TreeNode(9);
tree2.root?.left?.right?.left?.left?.left = TreeNode(6);
tree2.root?.left?.right?.right = TreeNode(8);
tree2.root?.left?.right?.right?.right = TreeNode(1);
tree2.root?.left?.right?.right?.right?.right = TreeNode(5);
tree2.root?.left?.left = TreeNode(2);
tree2.root?.right = TreeNode(7);
// Case 2
tree2.longestLeafToLeaf();
}input
9 10 3 -4 4 7 12 5 15
6 9 10 3 8 1 5Time Complexity
The time complexity of this algorithm is dominated by the recursive traversal of the binary tree to calculate the heights of internal nodes. This traversal takes O(n) time, where n is the number of nodes in the binary tree. The subsequent traversal to print the paths also contributes to O(n) time complexity. Overall, the time complexity of the algorithm is O(n).
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