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
2.2.1.
Complexity analysis
3.
Frequently Asked Questions
3.1.
What is the purpose of a tree data structure? 
3.2.
How do you find the binary tree's lowest common ancestor (LCA)?
3.3.
Describe a self-balanced tree?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Print all root leaf paths with their relative positions

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 understand tree data structure in brief and we will discuss the problem of printing all root leaf paths with their relative positions, we will discuss its algorithm, implementation, time complexity, and space complexity.

Binary Tree

The tree data structure is a hierarchical data structure organized in a tree-like structure. It is made up of a root node, structural nodes, and sub-nodes that are linked together via edges. 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 ones, finding any value in the tree is simple.  

                                 

Horizontal distance

The Horizontal Distance (HD) between two nodes indicates that they are on the same vertical line. HD is based on a basic concept. A right edge (edge linking to right subtree) is considered +1 horizontal distance and a left edge is considered -1 horizontal distance when the HD for root is 0. For example, in the given tree, HD is -2 for Node 4, -1 for Node 2, 0 for Nodes 5 and 6, and +2 for Node 7.

                    

Vertical order 

It is a method of traversing the elements of a binary tree – from top to bottom and left to right.      

                              

                                                                    Vertical order

Horizontal distance will be like, for root node it will be abs[0-(-2)]=2 and as follows for others.

Problem statement

We are given a binary tree, we have to print the root to the leaf path in a binary tree, by appending "~" to show the relative position.

Examples

 Input

        

Output

All root leaf paths with there relative positions:

~ ~ Q
~ W
R
------------
~ Q
W
~ T
------------
Q
~ E
Y
------------
Q
~ E
~ ~ U

 

In the above example, we are printing the root to the leaf path in a tree.

Approach

In the given problem, we will find the root leaf paths. To do this we will first find the preorder traversal of the tree. After that, we will calculate the horizontal distance on the order during traversal like in the example mentioned above. After that, we will print the path with a “~” sign at the end when we get to the leaf node. In the end, we will print all the nodes.

Algorithm

1. To solve this problem, we have created a function printAllwaysUtil which will take four arguments one as a node, second as ArrayList, third as distance, and fourth as order.

printAllwaysUtil will perform the preorder traversal by calling the root node, then the left tree node, and then the right tree node.

2. We have to calculate horizontal distances or HDs while traversing the tree. The horizontal distance is originally set to 0 for the root. For the left subtree, it is equal to the Horizontal Distance of the root minus 1. For the right subtree, it is equal to the Horizontal Distance of the root plus 1.

3. We save a list of nodes in an Arraylist for each HD value (" that will contain information about current node horizontal distance and root key-value "). 

4. We also keep track of the node order (order in which they appear in the path from the root to the leaf). 

5. We used ArrayList to keep the order in this case.

6. We print the node when we reach the leaf node during traversal by determining the current path's minimum horizontal distance.

After that, we'll follow the current path.

7. First, print the  "~" number, then find the absolute value by subtracting the current node horizontaldistance and minimum horizontaldistance.

Print the current node value.

8. Repeat the above steps for all leaf paths.

Java code

// Java program to print all root leaf paths
// ways with there relative position
import java.util.ArrayList;
import java.util.*;
class leafnode
{
 
    static final int MAX_way_SIZE = 1000;
 
    // tree structure
    static class Node
    {
        // char info;
        int info;
        Node prev, next;
    };
 
    // Function create new node
    static Node newNode(int info)
    {
        Node temp = new Node();
        temp.info = info;
        temp.prev = temp.next = null;
        return temp;
    }
 
    // Store way information
    static class way
    {
 
        // Horizontal distance of node from root.
        int horizontaldistance;
 
        // Store key
        int key;
 
    public
        way(int horizontaldistance, int key)
        {
            this.horizontaldistance = horizontaldistance;
            this.key = key;
        }
 
    public
        way()
        {
        }
    };
 
  
    static void printAllwaysUtil(Node root, ArrayList<way> Allway, int horizontaldistance, int order)
    {
        if (root == null)
            return;
 
        // Leaf node
        if (root.prev == null && root.next == null)
        {
 
            Allway.set(order, new way(horizontaldistance, root.info));
  
            int size=order+1;
            ArrayList<way>temp=new ArrayList<>(Allway);
            int minimum_horizontaldistance = Integer.MAX_VALUE;
 
            way p;
            int it=0;
            // Finding the minimum horizontal distance value
                while(it<size)
            
            {
                p = temp.get(it);
                if(minimum_horizontaldistance>p.horizontaldistance)
                minimum_horizontaldistance=p.horizontaldistance;
                it++;
            }
     
            // Print the root to leaf way with "_"
            // that indicate the related position
  
             it=0;
            while(it<size)
            {
     
                // Current tree node
                p = temp.get(it);
                int noOfUnderScores = Math.abs(
                    p.horizontaldistance - minimum_horizontaldistance);
     
                // Printing "~"
                for (int i = 0; i < noOfUnderScores; i++)
                      // Prints given root to leaf way with "~"
                  System.out.print("~");
     
                // Print current key
                System.out.println(p.key);
            it++;
            }
            System.out.println("_________________________");
            return;
        }
 
        Allway.set(order, new way(horizontaldistance, root.info));
 
        // Calling prev sub_tree
        printAllwaysUtil(root.prev, Allway,
                         horizontaldistance - 1, order + 1);
 
        printAllwaysUtil(root.next, Allway,
                         horizontaldistance + 1, order + 1);
    }
    // Driver code
public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the root element of the tree");
        Node root = newNode(sc.nextInt());
        System.out.println("Enter the root left element of the tree");
        root.prev = newNode(sc.nextInt());
        System.out.println("Enter the root right element of the tree");
        root.next = newNode(sc.nextInt());
        System.out.println("Enter the root left left element of the tree");
        root.prev.prev = newNode(sc.nextInt());
        System.out.println("Enter the root right left element of the tree");
        root.next.prev = newNode(sc.nextInt());
        System.out.println("Enter the root right right element of the tree");
        root.next.next = newNode(sc.nextInt());
        // printing the root leaf paths node with their relative positions.
        System.out.println("\nPRINTING THE ROOT TO LEAF NODE WITH THERE RELATIVE POSITION");
 
        // Base case
        if (root == null)
            return;
 
        ArrayList<way> Allways = new ArrayList<>();
        for (int i = 0; i < MAX_way_SIZE; i++)
        {
            Allways.add(new way());
        }
        printAllwaysUtil(root, Allways, 0, 0);
    }
}

 

Output

                                   

 

Complexity analysis

Time complexity

O(N), since we are using one loop to find the root to leaf path, where N is the number of nodes in the tree.

Space complexity

O(N), since we are using n number of nodes to store and build a tree to find the root to leaf paths.

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 the purpose of a tree data structure? 

 It is the hierarchical data, such as folder structure, organization structure, and XML/HTML data should be stored. A Binary Search Tree is a tree that allows you to quickly search, insert, and delete data that has been sorted. It also helps you to find the object that is nearest to you. Heap is a tree data structure that uses arrays and is used to construct priority queues.

How do you find the binary tree's lowest common ancestor (LCA)?

Let's look at two binary tree nodes, n1 and n2.

The shared ancestor of n1 and n2 that is positioned farthest from the root is known as the lowest common ancestor (LCA).

To locate the LCA, use the approach described below.

a) Create an array to store the path from the root node to n1.

b) Create an array to store the path from the root node to n2.

c) Follow both paths until the value in both arrays is the same.

Describe a self-balanced tree?

When insertion and deletion operations are performed, self-balanced binary search trees retain their height as minimal as possible.

To be self-balanced, a BST must constantly obey the BST rules, with the left subtree having lower-valued values and the right subtree having high-valued keys.

This is accomplished by the use of two operations:

  1.  right rotation
  2.  left rotation

Conclusion

In this article, we have discussed the tree data structure in brief, horizontal distances, vertical order, and how to print all root leaf paths with their relative positions with O(N) time and space complexities.

After reading about how to print all root leaf paths with their relative positions, are you not feeling excited to read/explore more articles on the topic of file systems? Don't worry; Coding Ninjas has you covered. To practice the questions on trees you can follow these questions on code studio Diagonal AnagramPartial BST, BST queriesGuess the price.

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
Print all Root-to-Leaf Paths with Maximum Count of Even Nodes
Next article
Print all full nodes in a Binary Tree
Live masterclass