Skip to main content

Print the longest path from root to leaf in a binary tree

Printing the longest path from the root node to a leaf node in a binary tree using recursion involves finding the path with the maximum number of nodes from the root node to a leaf node, and then printing the values of the nodes on that 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
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment