Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem statement
1.2.
Examples
2.
Approach
2.1.
Algorithm 
2.2.
Java code Implementation
2.2.1.
Complexity analysis
3.
Frequently Asked Questions
3.1.
What is a tree data structure?
3.2.
What is the main difference between a binary search tree and a tree binary tree?
3.3.
Define red black data structure?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Print longest leaf to leaf paths in a binary tree

Author Ashish Sharma
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a tree data structure?

The tree is a recursive definition of a non-linear data structure that arranges data in a hierarchical pattern. A tree is a graph with no circuits that are connected. When every pair of vertices in a graph has only one path between them, the graph is termed a tree.

What is the main difference between a binary search tree and a tree binary tree?

A Binary Tree is a basic structure with the simple constraint that no parent can have more than two children, but a Binary Search Tree is a version of the binary tree that organizes the nodes in a specific order.

Define red black data structure?

The characteristics of the Red-Black tree, a unique variety of self-balancing trees, include:

  1. Red or black are the two colors that each node can have.
  2. Always black is the root node.
  3. There can't be a red parent or red child for a red node.
  4. The number of black nodes on each path from the root node to a NULL node is the same.

Conclusion

In this article, we have discussed the binary tree data structure in brief, the diameter of a binary tree, and how to print the largest leaf to leaf paths in a binary tree by finding the diameter of the tree with O(N) time and space complexities.

After reading about how to print the largest leaf to leaf paths in a binary tree., are you not feeling excited to read/explore more articles on the topic of file systems? Don't worry; Coding Ninjas has you covered. If you want to practice questions on the binary tree then follow these links: Symmetric treeBST to sorted DLLPreorder binary tree, and Preorder traversal.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Lowest Common Ancestor in Binary Tree using RMQ
Next article
Count Nodes having the Highest Value in the Path from the Root to itself in a Binary Tree
Live masterclass