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.
84+ registered