Skip to main content

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

  1. Define a class TreeNode to represent a node in the binary tree. Each node will have a data value, a reference to its left child, and a reference to its right child.

  2. Define a class InternalNodeHeight to store the height of internal nodes along with their parent nodes.

  3. Create a BinaryTree class 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.
  4. In the main method:

    • Create a binary tree instance.
    • Construct the binary tree by adding nodes and connecting them.
    • Call the longestLeafToLeaf method 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 5

Time 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).





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