Bottom view of a binary tree in Java
The lowest nodes in their horizontal distance are present and referred to as the bottom view of a binary tree. The horizontal distance between the nodes of a binary tree is described as follows:
The horizontal length of the root is zero. The left child's horizontal distance equals its parent's horizontal distance minus one.
For the level order traversal, place tree nodes in a queue. Start with the root node's horizontal distance (hd) as 0, then add a left child to the line along with the horizontal distance (hd-1) and the correct child with the horizontal distance (hd+1).
Regarding the level order traversal, place tree nodes in a queue. Start with the root node's horizontal distance (hd) as 0, then add a left child to the line along with the horizontal distance (hd-1) and the correct child with the horizontal distance (hd+1).
Use the horizontal distance node data as the key whenever a new or existing horizontal distance is detected. It will first add it to the map before replacing the value the next time. This will guarantee that the piece at the bottom of that horizontal distance is visible on the map, so you will see it if you look at the Tree from below. Finally, go over the map's keys and publish their corresponding values.
Printing the Binary Tree's Bottom view involves the steps listed below.
- Set the variable hd to equal 0, map m with an int-int key-value pair, and queue q to level-wise store nodes.
- Push root in q and set root->hd = hd.
- While loop, continue till q is empty.
- Store the front element in the temp node, store the temp ->hd variable in the variable hd, pop it, and then set temp->data as the value for the hd key in the m variable, i.e. m[hd] = temp->data.
- If temp -> left is present and not NULL, set temp->left->hd to hd-1; likewise, if temp -> right is present and not NULL, put temp->right->hd to hd+1.
- Print the values after iterating through the keys.
BottomView.java
// Print the bottom View of the binary Tree using a Java program.
import java.util.*;
import java.util.Map.Entry;
// Tree node type
class Node
{
int data; // the node's data
int hd; // the node's horizontal distance
Node left, right; // allusions to the left and right.
// Builder of tree nodes
public Node (int key)
{
data = key;
hd = Integer.MAX_VALUE;
left = right = null;
}
}
// Tree type
class Tree
{
Node root; // root of the Tree
// Default constructor
public Tree() {}
// Parameterized tree constructor
public Tree(Node node)
{
root = node;
}
// a process for printing the bottom view.
public void bottomView()
{
if (root == null)
return;
// Set the root element's initial value for the variable "hd" to zero.
int hd = 0;
// TreeMap that organizes key-value pairs by key value
Map<Integer, Integer> map = new TreeMap<>();
//Tree node storage queue for level order traversal
Queue<Node> queue = new LinkedList<Node>();
// Give root the initialization value for the horizontal distance.
//Node and put it on the waiting list.
root.hd = hd;
queue.add(root);
// Continue until the wait is empty (standard level order loop)
while (!queue.isEmpty())
{
Node temp = queue.remove();
// Calculate the horizontal distance using the
// tree node in deque.
hd = temp.hd;
// Place the dequeued tree node in the TreeMap with the key.
// as horizontal separation. whenever we discover a node
// requiring replacement with the same horizontal distance
// information on the map.
map.put(hd, temp.data);
// Add the left child of the dequeued Node if it has one.
// a line with a hd-1 horizontal distance.
if (temp.left != null)
{
temp.left.hd = hd-1;
queue.add(temp.left);
}
// If the dequeued Node has the right child, add it to the
// a line with a hd-1 horizontal distance.
if (temp.right != null)
{
temp.right.hd = hd+1;
queue.add(temp.right);
}
}
// Extract the map's entries into a set and traverse it.
// over that, an iterator.
Set<Entry<Integer, Integer>> set = map.entrySet();
Iterator<Entry<Integer, Integer>> iterator = set.iterator();
//Utilize the iterator to navigate the map's elements.
while (iterator.hasNext())
{
Map.Entry<Integer, Integer> me = iterator.next();
System.out.print(me.getValue()+" ");
}
}
}
public class BottomView
{
public static void main(String[] args)
{
Node root = new Node(10);
root.left = new Node(7);
root.right = new Node(16);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(3);
root.right.right = new Node(22);
root.left.right.left = new Node(13);
root.left.right.right = new Node(12);
Tree tree = new Tree(root);
System.out.println("Bottom view of the given binary tree:");
tree.bottomView();
}
}
Output:
The bottom view of a binary tree is:
4 13 3 12 22