Introduction
In this article, we will discuss binary tree data structure in brief, the diameter of a tree, how to print the longest leaf to leaf paths in a binary tree, its approach, and time and space complexities.
Binary tree
In a binary tree, each node can have a maximum of two children and the tree is always in a sorted manner. Each node can have either zero, one, or two children. A binary tree is useful because it can generate a data structure that resembles a "yes/no" decision-making process. For example, if you create a binary tree to store numeric values with each left sub-tree containing larger values and each right sub-tree containing smaller values, it's simple to find any value in the tree.
Binary tree
Diameter of a tree
The longest path between any two nodes in a binary tree is the diameter of the tree. This path might or might not go all the way to the root. The number of edges between two nodes represents the length of a path between them.
Diameter of tree
Problem statement
We are given a binary tree, we have to print the longest leaf to leaf paths in the tree.
Examples
Input
Output
Longest leaf to leaf path = {7, 6, 9, 10} or {8, 6, 9, 10}
Input
Output
Longest leaf to leaf path = {1, 2, 3, 4, 5}
In the above example, we are printing the root to the leaf path in a tree by finding the diameter of the tree.
Approach
In the given problem, we will find the longest leaf-to-leaf paths. To do this first, we will try to find the diameter of the binary tree. We will find the diameter by the height function and with the formula (left height+right height+1) for each node. After that, on the left side, we discover the longest root to leaf path, and similarly on the right side. Finally, the left side path, root, and right side path are printed respectively.
Algorithm
1. To solve this problem, we have created two functions first is a printing array and the second is a printing path.
2. Printing function has two arguments first one is a character array, the second is an integer, and the printing path function has four arguments one is the root node, the second is a character array, third and fourth are integers.
3. We will find the diameter of the binary tree by using the height criteria, for each node with the help of the following formula:
(leftheight + rightheight + 1)
4. In the printing path function, we are finding out all the root to leaf paths by making two recursive calls one for left and another for right.
5. We print that root to leaf path which is equal to the height and distance of the tree.
6. In the printing array function we are printing the left path of the root by applying a loop condition that (i<pathdistance) where i=0 and incrementing in each iteration.
7. Finally, we will print the left side path, root, and right side path respectively.
Java code Implementation
// Java code to print the longest leaf to leaf paths
import java.io.*;
import java.util.*;
// node structure
class Node
{
char value;
Node left, right;
Node(char val)
{
value = val;
left = null;
right = null;
}
}
class leafnode2
{
static int answer, leftheight, rightheight, m;
static Node k;
public static Node Root;
// find heightdistance of a tree
static int heightdistance(Node root)
{
if (root == null)
return 0;
int right_heightdistance = heightdistance(root.right);
int left_heightdistance = heightdistance(root.left);
// updating the answer
if (answer < 1 + left_heightdistance + right_heightdistance)
{
k = root;
rightheight = right_heightdistance;
leftheight = left_heightdistance;
answer = 1 + left_heightdistance + right_heightdistance;
// saving the heightdistance of left & right subtree as well.
}
return 1 + ((left_heightdistance>right_heightdistance)?left_heightdistance:right_heightdistance);
}
// prints the root to leaf
static void printingArray(char[] ints, int length)
{
int i;
// printing the left part of the path in reverse order
if (m == 1)
{ i=0;
while(i<length)
{
System.out.print(ints[i] + " ");
i++;
}
}
else if (m == 0)
{
i=length-1;
while(i>=0)
{
System.out.print(ints[i] + " ");
i--;
}
}
}
// finding out all the root to leaf paths
static void printingpath(Node node, char[] path, int pathdistance, int maximum)
{
if (node == null)
return;
// appending this node to the path array
path[pathdistance] = node.value;
pathdistance++;
if(node.left != null && node.right != null)
{
printingpath(node.left, path, pathdistance, maximum);
printingpath(node.right, path, pathdistance, maximum);
}
else if (node.left == null && node.right == null)
{
// printing only one path which is equal to the
// heightdistance of the tree.
if (pathdistance == maximum && (m == 0 || m == 1))
{
printingArray(path, pathdistance);
m = 2;
}
}
}
// Driver code
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the root element of the tree");
leafnode2.Root = new Node(sc.next().charAt(0));
System.out.println("Enter the root left element of the tree");
leafnode2.Root.left = new Node(sc.next().charAt(0));
System.out.println("Enter the root.right element of the tree");
leafnode2.Root.right = new Node(sc.next().charAt(0));
System.out.println("Enter the root.left.left element of the tree");
leafnode2.Root.left.left = new Node(sc.next().charAt(0));
System.out.println("Enter the root.left.right element of the tree");
leafnode2.Root.left.right = new Node(sc.next().charAt(0));
System.out.println("Enter the root.left.right.left element of the tree");
leafnode2.Root.left.right.left = new Node(sc.next().charAt(0));
System.out.println("Enter the root.left.right.right element of the tree");
leafnode2.Root.left.right.right = new Node(sc.next().charAt(0));
System.out.println("Enter the root.left.left.right element of the tree");
leafnode2.Root.left.left.right = new Node(sc.next().charAt(0));
System.out.println("Enter the root.left.left.right.left element of the tree");
leafnode2.Root.left.left.right.left = new Node(sc.next().charAt(0));
// printing the longest leaf to leaf paths in a binary tree
System.out.println("\nPRINTING THE LONGEST LEAF TO LEAF PATHS IN A BINARY TREE");
// Computing the diameter of a binary tree.
if (Root == null)
return;
// leftheight will store heightdistance of left subtree
// rightheight will store heightdistance of right subtree
answer = Integer.MIN_VALUE;
leftheight = 0;
rightheight = 0;
m = 0;
int heightdistance_of_tree = heightdistance(Root);
char[] lPath = new char[100];
int pathdistance = 0;
// printing the left part of the diameter
printingpath(k.left, lPath, pathdistance, leftheight);
System.out.print(k.value + " ");
char[] rightPath = new char[100];
m = 1;
// printing the right part of the diameter
printingpath(k.right, rightPath, pathdistance, rightheight);
}
}
Output
Complexity analysis
Time complexity
O(N), since we are traversing all the nodes once by doing a simple dfs (depth-first search) and to print the longest leaf to leaf paths we are again doing a dfs hence the time complexity would be O(N).
Space complexity
O(N), since we are using N number of nodes to store the data of the tree and build the tree.
34+ registered 
