Print the longest path from root to leaf in a binary tree
The problem entails a binary tree, and the objective is to identify and print the longest path from the root to a leaf node in the tree. This involves finding the path that traverses the maximum number of nodes from the root to a leaf.
Problem Statement
Given a binary tree, we are tasked with identifying the longest path from the root to a leaf node and printing that path.
Example
Consider the binary tree illustrated in the code:
4
/ \
9 7
/ \ \
2 5 12
/ \ / \
6 8 5 18
/ / \
19 3 15
\ \
10 1
For this tree, the longest paths from the root to leaf nodes are:
- Path: 4 -> 9 -> 5 -> 8 -> 3 -> 10
- Path: 4 -> 7 -> 12 -> 5 -> 15 -> 1
Idea to Solve
The problem can be addressed using a recursive approach. We begin at the root of the binary tree and traverse it while keeping track of the current path. When we reach a leaf node, we compare the length of the current path with the length of the longest path encountered so far. If the current path is longer, we update the longest path. After processing a node, we move to its left and right children recursively.
Pseudocode
function printPath(path):
for element in path:
print element
print newline
function findLongestPath(node, path, longestPath):
if node is null:
return
add node.data to path
if node is leaf node:
if length of path > length of longestPath:
copy path to longestPath
else:
findLongestPath(node.left, path, longestPath)
findLongestPath(node.right, path, longestPath)
remove last element from path
function longestPaths():
create empty path list
create empty longestPath list
if root is null:
return
else:
call findLongestPath(root, path, longestPath)
printPath(longestPath)
main:
create binary tree
construct tree as shown
call longestPaths()
Algorithm Explanation
- The
printPath
function simply prints the elements of the given path. - The
findLongestPath
function recursively traverses the binary tree, adding elements to the current path. When a leaf node is reached, it compares the length of the current path with the length of the longest path encountered so far. If the current path is longer, it updates the longest path. - The
longestPaths
function initializes empty path and longestPath lists, and then callsfindLongestPath
with the root node. - In the
main
function, a binary tree is constructed, andlongestPaths
is called to identify and print the longest path.
Program Solution
import java.util.ArrayList;
/*
Java Program
Print the longest path from root to leaf 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;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
// Display given path
public void printPath(ArrayList < Integer > path)
{
int i = 0;
// print path
while (i < path.size())
{
System.out.print(" " + path.get(i));
i++;
}
System.out.print("\n");
}
// Find height of given binary tree
public int treeHeight(TreeNode node)
{
if (node != null)
{
int a = treeHeight(node.left);
int b = treeHeight(node.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Find all longest path using recursion
public void findLongestPath(TreeNode node,
ArrayList < Integer > path, int height)
{
if (node == null)
{
return;
}
// Add path element
path.add(node.data);
if (node.left == null && node.right == null)
{
if (height == 0)
{
printPath(path);
}
}
else
{
findLongestPath(node.left, path, height - 1);
findLongestPath(node.right, path, height - 1);
}
// Remove last node in path
path.remove(path.size() - 1);
}
// Handles the request of finding longest path in tree
public void longestPaths()
{
// This is use to collect sort path
ArrayList < Integer > path = new ArrayList < Integer > ();
if (this.root == null)
{
// Empty Tree
return;
}
else
{
findLongestPath(this.root, path, treeHeight(this.root)-1);
}
}
public static void main(String[] args)
{
// Create new binary tree
BinaryTree tree = new BinaryTree();
/*
4
/ \
9 7
/ \ \
2 5 12
/ \ / \
6 8 5 18
/ / \
19 3 15
\ \
10 1
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(5);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(19);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.right.right.left = new TreeNode(3);
tree.root.left.right.right.left.right = new TreeNode(10);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(18);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);
tree.root.right.right.left.right.right = new TreeNode(1);
tree.longestPaths();
}
}
input
4 9 5 8 3 10
4 7 12 5 15 1
// Include header file
#include <iostream>
#include <vector>
using namespace std;
/*
C++ Program
Print the longest path from root to leaf 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 BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
// Display given path
void printPath(vector < int > path)
{
int i = 0;
// print path
while (i < path.size())
{
cout << " " << path.at(i);
i++;
}
cout << "\n";
}
// Find height of given binary tree
int treeHeight(TreeNode *node)
{
if (node != NULL)
{
int a = this->treeHeight(node->left);
int b = this->treeHeight(node->right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Find all longest path using recursion
void findLongestPath(TreeNode *node, vector < int > path, int height)
{
if (node == NULL)
{
return;
}
// Add path element
path.push_back(node->data);
if (node->left == NULL && node->right == NULL)
{
if (height == 0)
{
this->printPath(path);
}
}
else
{
this->findLongestPath(node->left, path, height - 1);
this->findLongestPath(node->right, path, height - 1);
}
// Remove last node in path
path.pop_back();
}
// Handles the request of finding longest path in tree
void longestPaths()
{
// This is use to collect sort path
vector < int > path;
if (this->root == NULL)
{
// Empty Tree
return;
}
else
{
this->findLongestPath(this->root, path, this->treeHeight(this->root) - 1);
}
}
};
int main()
{
// Create new binary tree
BinaryTree *tree = new BinaryTree();
/*
4
/ \
9 7
/ \ \
2 5 12
/ \ / \
6 8 5 18
/ / \
19 3 15
\ \
10 1
-----------------
Constructing binary tree
*/
tree->root = new TreeNode(4);
tree->root->left = new TreeNode(9);
tree->root->left->right = new TreeNode(5);
tree->root->left->right->left = new TreeNode(6);
tree->root->left->right->left->left = new TreeNode(19);
tree->root->left->right->right = new TreeNode(8);
tree->root->left->right->right->left = new TreeNode(3);
tree->root->left->right->right->left->right = new TreeNode(10);
tree->root->left->left = new TreeNode(2);
tree->root->right = new TreeNode(7);
tree->root->right->right = new TreeNode(12);
tree->root->right->right->right = new TreeNode(18);
tree->root->right->right->left = new TreeNode(5);
tree->root->right->right->left->right = new TreeNode(15);
tree->root->right->right->left->right->right = new TreeNode(1);
tree->longestPaths();
return 0;
}
input
4 9 5 8 3 10
4 7 12 5 15 1
// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program
Print the longest path from root to leaf 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 BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
// Display given path
public void printPath(List < int > path)
{
int i = 0;
// print path
while (i < path.Count)
{
Console.Write(" " + path[i]);
i++;
}
Console.Write("\n");
}
// Find height of given binary tree
public int treeHeight(TreeNode node)
{
if (node != null)
{
int a = this.treeHeight(node.left);
int b = this.treeHeight(node.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Find all longest path using recursion
public void findLongestPath(TreeNode node, List < int > path, int height)
{
if (node == null)
{
return;
}
// Add path element
path.Add(node.data);
if (node.left == null && node.right == null)
{
if (height == 0)
{
this.printPath(path);
}
}
else
{
this.findLongestPath(node.left, path, height - 1);
this.findLongestPath(node.right, path, height - 1);
}
// Remove last node in path
path.RemoveAt(path.Count - 1);
}
// Handles the request of finding longest path in tree
public void longestPaths()
{
// This is use to collect sort path
List < int > path = new List < int > ();
if (this.root == null)
{
// Empty Tree
return;
}
else
{
this.findLongestPath(this.root, path,
this.treeHeight(this.root) - 1);
}
}
public static void Main(String[] args)
{
// Create new binary tree
BinaryTree tree = new BinaryTree();
/*
4
/ \
9 7
/ \ \
2 5 12
/ \ / \
6 8 5 18
/ / \
19 3 15
\ \
10 1
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(5);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(19);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.right.right.left = new TreeNode(3);
tree.root.left.right.right.left.right = new TreeNode(10);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(18);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);
tree.root.right.right.left.right.right = new TreeNode(1);
tree.longestPaths();
}
}
input
4 9 5 8 3 10
4 7 12 5 15 1
<?php
/*
Php Program
Print the longest path from root to leaf 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 BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
// Display given path
public function printPath($path)
{
$i = 0;
// print path
while ($i < count($path))
{
echo(" ".$path[$i]);
$i++;
}
echo("\n");
}
// Find height of given binary tree
public function treeHeight($node)
{
if ($node != NULL)
{
$a = $this->treeHeight($node->left);
$b = $this->treeHeight($node->right);
if ($a > $b)
{
return $a + 1;
}
else
{
return $b + 1;
}
}
else
{
return 0;
}
}
// Find all longest path using recursion
public function findLongestPath($node, $path, $height)
{
if ($node == NULL)
{
return;
}
// Add path element
$path[] = $node->data;
if ($node->left == NULL && $node->right == NULL)
{
if ($height == 0)
{
$this->printPath($path);
}
}
else
{
$this->findLongestPath($node->left, $path, $height - 1);
$this->findLongestPath($node->right, $path, $height - 1);
}
// Remove last node in path
array_pop($path);
}
// Handles the request of finding longest path in tree
public function longestPaths()
{
// This is use to collect sort path
$path = array();
if ($this->root == NULL)
{
// Empty Tree
return;
}
else
{
$this->findLongestPath($this->root,
$path, $this->treeHeight($this->root) - 1);
}
}
}
function main()
{
// Create new binary tree
$tree = new BinaryTree();
/*
4
/ \
9 7
/ \ \
2 5 12
/ \ / \
6 8 5 18
/ / \
19 3 15
\ \
10 1
-----------------
Constructing binary tree
*/
$tree->root = new TreeNode(4);
$tree->root->left = new TreeNode(9);
$tree->root->left->right = new TreeNode(5);
$tree->root->left->right->left = new TreeNode(6);
$tree->root->left->right->left->left = new TreeNode(19);
$tree->root->left->right->right = new TreeNode(8);
$tree->root->left->right->right->left = new TreeNode(3);
$tree->root->left->right->right->left->right = new TreeNode(10);
$tree->root->left->left = new TreeNode(2);
$tree->root->right = new TreeNode(7);
$tree->root->right->right = new TreeNode(12);
$tree->root->right->right->right = new TreeNode(18);
$tree->root->right->right->left = new TreeNode(5);
$tree->root->right->right->left->right = new TreeNode(15);
$tree->root->right->right->left->right->right = new TreeNode(1);
$tree->longestPaths();
}
main();
input
4 9 5 8 3 10
4 7 12 5 15 1
/*
Node JS Program
Print the longest path from root to leaf in a binary tree
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
// Display given path
printPath(path)
{
var i = 0;
// print path
while (i < path.length)
{
process.stdout.write(" " + path[i]);
i++;
}
process.stdout.write("\n");
}
// Find height of given binary tree
treeHeight(node)
{
if (node != null)
{
var a = this.treeHeight(node.left);
var b = this.treeHeight(node.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Find all longest path using recursion
findLongestPath(node, path, height)
{
if (node == null)
{
return;
}
// Add path element
path.push(node.data);
if (node.left == null && node.right == null)
{
if (height == 0)
{
this.printPath(path);
}
}
else
{
this.findLongestPath(node.left, path, height - 1);
this.findLongestPath(node.right, path, height - 1);
}
// Remove last node in path
path.pop();
}
// Handles the request of finding longest path in tree
longestPaths()
{
// This is use to collect sort path
var path = [];
if (this.root == null)
{
// Empty Tree
return;
}
else
{
this.findLongestPath(this.root,
path, this.treeHeight(this.root) - 1);
}
}
}
function main()
{
// Create new binary tree
var tree = new BinaryTree();
/*
4
/ \
9 7
/ \ \
2 5 12
/ \ / \
6 8 5 18
/ / \
19 3 15
\ \
10 1
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(5);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(19);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.right.right.left = new TreeNode(3);
tree.root.left.right.right.left.right = new TreeNode(10);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(18);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);
tree.root.right.right.left.right.right = new TreeNode(1);
tree.longestPaths();
}
main();
input
4 9 5 8 3 10
4 7 12 5 15 1
# Python 3 Program
# Print the longest path from root to leaf 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 BinaryTree :
def __init__(self) :
self.root = None
# Display given path
def printPath(self, path) :
i = 0
# print path
while (i < len(path)) :
print(" ", path[i], end = "")
i += 1
print(end = "\n")
# Find height of given binary tree
def treeHeight(self, node) :
if (node != None) :
a = self.treeHeight(node.left)
b = self.treeHeight(node.right)
if (a > b) :
return a + 1
else :
return b + 1
else :
return 0
# Find all longest path using recursion
def findLongestPath(self, node, path, height) :
if (node == None) :
return
# Add path element
path.append(node.data)
if (node.left == None and node.right == None) :
if (height == 0) :
self.printPath(path)
else :
self.findLongestPath(node.left, path, height - 1)
self.findLongestPath(node.right, path, height - 1)
# Remove last node in path
del path[len(path) - 1]
# Handles the request of finding longest path in tree
def longestPaths(self) :
# This is use to collect sort path
path = []
if (self.root == None) :
# Empty Tree
return
else :
self.findLongestPath(self.root,
path, self.treeHeight(self.root) - 1)
def main() :
# Create new binary tree
tree = BinaryTree()
# 4
# / \
# 9 7
# / \ \
# 2 5 12
# / \ / \
# 6 8 5 18
# / / \
# 19 3 15
# \ \
# 10 1
# -----------------
# Constructing binary tree
tree.root = TreeNode(4)
tree.root.left = TreeNode(9)
tree.root.left.right = TreeNode(5)
tree.root.left.right.left = TreeNode(6)
tree.root.left.right.left.left = TreeNode(19)
tree.root.left.right.right = TreeNode(8)
tree.root.left.right.right.left = TreeNode(3)
tree.root.left.right.right.left.right = TreeNode(10)
tree.root.left.left = TreeNode(2)
tree.root.right = TreeNode(7)
tree.root.right.right = TreeNode(12)
tree.root.right.right.right = TreeNode(18)
tree.root.right.right.left = TreeNode(5)
tree.root.right.right.left.right = TreeNode(15)
tree.root.right.right.left.right.right = TreeNode(1)
tree.longestPaths()
if __name__ == "__main__": main()
input
4 9 5 8 3 10
4 7 12 5 15 1
# Ruby Program
# Print the longest path from root to leaf 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 BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
# Display given path
def printPath(path)
i = 0
# print path
while (i < path.length)
print(" ", path[i])
i += 1
end
print("\n")
end
# Find height of given binary tree
def treeHeight(node)
if (node != nil)
a = self.treeHeight(node.left)
b = self.treeHeight(node.right)
if (a > b)
return a + 1
else
return b + 1
end
else
return 0
end
end
# Find all longest path using recursion
def findLongestPath(node, path, height)
if (node == nil)
return
end
# Add path element
path.push(node.data)
if (node.left == nil && node.right == nil)
if (height == 0)
self.printPath(path)
end
else
self.findLongestPath(node.left, path, height - 1)
self.findLongestPath(node.right, path, height - 1)
end
# Remove last node in path
path.delete_at(path.length - 1)
end
# Handles the request of finding longest path in tree
def longestPaths()
# This is use to collect sort path
path = []
if (self.root == nil)
# Empty Tree
return
else
self.findLongestPath(self.root,
path, self.treeHeight(self.root) - 1)
end
end
end
def main()
# Create new binary tree
tree = BinaryTree.new()
# 4
# / \
# 9 7
# / \ \
# 2 5 12
# / \ / \
# 6 8 5 18
# / / \
# 19 3 15
# \ \
# 10 1
# -----------------
# Constructing binary tree
tree.root = TreeNode.new(4)
tree.root.left = TreeNode.new(9)
tree.root.left.right = TreeNode.new(5)
tree.root.left.right.left = TreeNode.new(6)
tree.root.left.right.left.left = TreeNode.new(19)
tree.root.left.right.right = TreeNode.new(8)
tree.root.left.right.right.left = TreeNode.new(3)
tree.root.left.right.right.left.right = TreeNode.new(10)
tree.root.left.left = TreeNode.new(2)
tree.root.right = TreeNode.new(7)
tree.root.right.right = TreeNode.new(12)
tree.root.right.right.right = TreeNode.new(18)
tree.root.right.right.left = TreeNode.new(5)
tree.root.right.right.left.right = TreeNode.new(15)
tree.root.right.right.left.right.right = TreeNode.new(1)
tree.longestPaths()
end
main()
input
4 9 5 8 3 10
4 7 12 5 15 1
import scala.collection.mutable._;
/*
Scala Program
Print the longest path from root to leaf 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 BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Display given path
def printPath(path: ArrayBuffer[Int]): Unit = {
var i: Int = 0;
// print path
while (i < path.size)
{
print(" " + path(i));
i += 1;
}
print("\n");
}
// Find height of given binary tree
def treeHeight(node: TreeNode): Int = {
if (node != null)
{
var a: Int = treeHeight(node.left);
var b: Int = treeHeight(node.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Find all longest path using recursion
def findLongestPath(node: TreeNode, path:
ArrayBuffer[Int], height: Int): Unit = {
if (node == null)
{
return;
}
// Add path element
path += node.data;
if (node.left == null && node.right == null)
{
if (height == 0)
{
printPath(path);
}
}
else
{
findLongestPath(node.left, path, height - 1);
findLongestPath(node.right, path, height - 1);
}
// Remove last node in path
path.remove(path.size - 1);
}
// Handles the request of finding longest path in tree
def longestPaths(): Unit = {
// This is use to collect sort path
var path: ArrayBuffer[Int] = new ArrayBuffer[Int]();
if (this.root == null)
{
// Empty Tree
return;
}
else
{
findLongestPath(this.root, path, treeHeight(this.root) - 1);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create new binary tree
var tree: BinaryTree = new BinaryTree();
/*
4
/ \
9 7
/ \ \
2 5 12
/ \ / \
6 8 5 18
/ / \
19 3 15
\ \
10 1
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(5);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(19);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.right.right.left = new TreeNode(3);
tree.root.left.right.right.left.right = new TreeNode(10);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(18);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);
tree.root.right.right.left.right.right = new TreeNode(1);
tree.longestPaths();
}
}
input
4 9 5 8 3 10
4 7 12 5 15 1
import Foundation;
/*
Swift 4 Program
Print the longest path from root to leaf 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 BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Display given path
func printPath(_ path: [Int])
{
var i = 0;
// print path
while (i < path.count)
{
print(" ", path[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// Find height of given binary tree
func treeHeight(_ node: TreeNode? ) -> Int
{
if (node != nil)
{
let a = self.treeHeight(node!.left);
let b = self.treeHeight(node!.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Find all longest path using recursion
func findLongestPath(_ node: TreeNode? , _ path : inout[Int], _ height: Int)
{
if (node == nil)
{
return;
}
// Add path element
path.append(node!.data);
if (node!.left == nil && node!.right == nil)
{
if (height == 0)
{
self.printPath(path);
}
}
else
{
self.findLongestPath(node!.left, &path, height - 1);
self.findLongestPath(node!.right, &path, height - 1);
}
// Remove last node in path
path.removeLast();
}
// Handles the request of finding longest path in tree
func longestPaths()
{
// This is use to collect sort path
var path = [Int]();
if (self.root == nil)
{
// Empty Tree
return;
}
else
{
self.findLongestPath(self.root, &path,
self.treeHeight(self.root) - 1);
}
}
}
func main()
{
// Create new binary tree
let tree = BinaryTree();
/*
4
/ \
9 7
/ \ \
2 5 12
/ \ / \
6 8 5 18
/ / \
19 3 15
\ \
10 1
-----------------
Constructing binary tree
*/
tree.root = TreeNode(4);
tree.root!.left = TreeNode(9);
tree.root!.left!.right = TreeNode(5);
tree.root!.left!.right!.left = TreeNode(6);
tree.root!.left!.right!.left!.left = TreeNode(19);
tree.root!.left!.right!.right = TreeNode(8);
tree.root!.left!.right!.right!.left = TreeNode(3);
tree.root!.left!.right!.right!.left!.right = TreeNode(10);
tree.root!.left!.left = TreeNode(2);
tree.root!.right = TreeNode(7);
tree.root!.right!.right = TreeNode(12);
tree.root!.right!.right!.right = TreeNode(18);
tree.root!.right!.right!.left = TreeNode(5);
tree.root!.right!.right!.left!.right = TreeNode(15);
tree.root!.right!.right!.left!.right!.right = TreeNode(1);
tree.longestPaths();
}
main();
input
4 9 5 8 3 10
4 7 12 5 15 1
/*
Kotlin Program
Print the longest path from root to leaf 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 BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// Display given path
fun printPath(path: MutableList<Int> ): Unit
{
var i: Int = 0;
// print path
while (i < path.size)
{
print(" " + path[i]);
i += 1;
}
print("\n");
}
// Find height of given binary tree
fun treeHeight(node: TreeNode ? ): Int
{
if (node != null)
{
val a: Int = this.treeHeight(node.left);
val b: Int = this.treeHeight(node.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Find all longest path using recursion
fun findLongestPath(node: TreeNode ? ,
path : MutableList<Int> , height : Int): Unit
{
if (node == null)
{
return;
}
// Add path element
path.add(node.data);
if (node.left == null && node.right == null)
{
if (height == 0)
{
this.printPath(path);
}
}
else
{
this.findLongestPath(node.left, path, height - 1);
this.findLongestPath(node.right, path, height - 1);
}
// Remove last node in path
path.removeAt(path.size - 1);
}
// Handles the request of finding longest path in tree
fun longestPaths(): Unit
{
// This is use to collect sort path
var path = mutableListOf<Int>();
if (this.root == null)
{
// Empty Tree
return;
}
else
{
this.findLongestPath(this.root,
path, this.treeHeight(this.root) - 1);
}
}
}
fun main(args: Array < String > ): Unit
{
// Create new binary tree
val tree: BinaryTree = BinaryTree();
/*
4
/ \
9 7
/ \ \
2 5 12
/ \ / \
6 8 5 18
/ / \
19 3 15
\ \
10 1
-----------------
Constructing binary tree
*/
tree.root = TreeNode(4);
tree.root?.left = TreeNode(9);
tree.root?.left?.right = TreeNode(5);
tree.root?.left?.right?.left = TreeNode(6);
tree.root?.left?.right?.left?.left = TreeNode(19);
tree.root?.left?.right?.right = TreeNode(8);
tree.root?.left?.right?.right?.left = TreeNode(3);
tree.root?.left?.right?.right?.left?.right = TreeNode(10);
tree.root?.left?.left = TreeNode(2);
tree.root?.right = TreeNode(7);
tree.root?.right?.right = TreeNode(12);
tree.root?.right?.right?.right = TreeNode(18);
tree.root?.right?.right?.left = TreeNode(5);
tree.root?.right?.right?.left?.right = TreeNode(15);
tree.root?.right?.right?.left?.right?.right = TreeNode(1);
tree.longestPaths();
}
input
4 9 5 8 3 10
4 7 12 5 15 1
Time Complexity
The time complexity of the solution is mainly determined by the number of nodes in the binary tree, as we traverse each node once. In the worst case, we would traverse all paths from the root to the leaf nodes, resulting in a time complexity of O(n), where n is the number of nodes in the binary tree.
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