Bottom View of Binary Tree
Bottom view of the binary tree results in nodes that are visible from the bottom of the tree.
Binary Tree
A binary tree is a non-linear data structure in which every node has at a most maximum of two children. So, in terms of binary tree construction, we should have a node with three-pointers one to hold data and two for left and right nodes.
In a binary search tree, the values are inserted based upon the properties left node contains values that are less than the root node and the right node contains values greater than the root node.
Binary Search Tree
class Bst {
public class Node {
int data;
Node right;
Node left;
int height;
Node(int data, int height) {
this.height = height;
this.data = data;
left = right = null;
}
}
The above program has a constructor node for inserting data, on every insertion, it assigns the node with data and left, right as null with height zero. If the value is less than the root node it assigns the value to the left of the root and height is reduced by 1 and for the right, the height is increased by 1.
public static Node root;
public void insert(int data) {
root = insertRecusrive(root, data, 0);
}
public Bst.Node insertRecusrive(Node root, int data, int height) {
if (root == null) {
root = new Bst().new Node(data, height);
return root;
} else if (data < root.data) {
root.left = insertRecusrive(root.left, data, root.height - 1);
} else if (data > root.data) {
root.right = insertRecusrive(root.right, data, root.height + 1);
}
return root;
}
Algorithm:
- In every insertion check if the value is greater than the node or less than the node.
- If it is less than the value of the root node then make a recursive call till the root is null on the left side and assign it with value and in every recursive call, the height is reduced by -1.
- If it is greater than the value of the root node then make a recursive call till the root is null on the right side and assign it with value and in every recursive call, the height is increased by 1.
- Create a map to hold the unique height values of node
- Traverse through the tree and check the value is in the map or not if it's unique print the value and add it to the map.
Map<Integer, Integer> m = new LinkedHashMap<>();
public void traversal(Node root) {
if (root.left != null) {
traversal(root.left);
}
if (root.right != null) {
traversal(root.right);
}
if (!m.containsKey(root.height)) {
m.put(root.height, root.data);
System.out.print(root.data + " ");
}
The bottom view of the tree is: 1 3 2 5
As 1 and 3 are on the same level from the bottom view 1 is not visible hence it is skipped.
I hope you guys liked this article, here are some other articles you may like:
0 Comments