Print the bottom view of Binary Tree
Given a binary tree, print the nodes that is visible, when the tree is viewed from the bottom.
Let us first understand what we want to achieve? what is the input and what will be the expected output?
Bottom view means, when we look the tree from the bottom, the nodes that are visible will be called the bottom view of the tree. So in the above image,
For Case 1, Node 4, 2, 6, 3, 7 will be visible from bottom and Node 1 and Node 5 will not be visible from bottom as it will be hidden by Node 6.
For Case 2, Node 2, 4, 5, 6 will be visible and Node 1 and Node 3 will not be visible from bottom as it will be hidden by Node 4 and Node 5 respectively.
Solution
Solution for printing the nodes visible from bottom view of binary tree is very similar to vertical traversal of binary tree.
Before proceeding with the solution, it is very important to understand,
How to print the binary tree in vertical order.
We will use the same concept that we used for vertical order traversal of Binary Tree.
If two nodes have the same Horizontal Distance from root, then they are on same vertical line.
Only difference we see in solution of vertical traversal of binary tree and printing the nodes that are visible from bottom view is,
In vertical traversal of binary tree.
1. We do Pre-order traversal of binary tree.
2. Nodes that are part of same horizontal distance are clubbed together in hashmap value against key
horizontal distance(hd).
For printing the nodes visible from bottom view, we are only interested in last node of each column or line because that are the only nodes that will be visible from bottom, others nodes will be hidden by them.
1. If we do Pre-order traversal that is depth first traversal, then we will not able to track which is
last node in a line. Lets understand with example,
Look at above tree, If we do Pre-order traversal, then,
Node 1 will be encountered first at Line 0 and we will store it in map.put(0, Node 1)
Node 2 will be encountered at Line -1 and we will store it in map.put(-1, Node 2)
Node 4 will be encountered at Line 0, we will override the Node 1 already present against
horizontal distance 0. It means this is the last element we encountered at line 0 till now.
Now map status is map.put(0, Node 4).
Node 5 will be encountered at Line 1 and we will store it in map.put(1, Node 5)
Node 6 will be encountered at Line 2 and we will store it in map.put(2, Node 6)
Node 3 will be encountered at Line 1 and we will override the Node 5 already present in map
thinking that this is the last node visited at line 1. map.put(1, Node 3)
We are in trouble here, So depth first traversal will not help.
We have to do Level order traversal here, which will process the tree level by level and make
sure that last element of each line/column will be encountered last.
2. In vertical order traversal, nodes that are part of same horizontal distance are clubbed together in
hashmap value against key hd.
Here, instead of clubbing the nodes present on same line, we will simply put the nodes of
each line in map and keep overriding nodes present on same line, which will make sure that all top
nodes of same line will arrive in map first and last node of same line will override the top nodes of
same line, and hence map will have last nodes of each line.
3. Print the map.
Algorithm
1. Read the tree in Level order traversal.
2. We will take one map, which will store last nodes of each line.
(for map, key will be horizontal distance(hd) and value will be last node of each line).
For each node encountered, check whether hd is already present in map,
If present, then we will override the node already present against the hd, as this is the last
node we encounter on same line till now.
If not present, then this is the first time we are encountering node of line, which might be last
node of a Line, so simply store it data against hd.
Point here is, every time we need to override the value(node) stored against the key(hd),
If we keep on overriding the value, then node entered at last in map will be last node of each
line.
5. Better to use TreeMap in this case, as it will store the result in ascending order,
which we are interested in.
(We can use TreeSet here, for simplicity I have used TreeMap).
6. Print map.
Java Program for printing nodes visible from bottom view of Binary tree.
BottomViewOfBinaryTree.java
package com.javabypatel.tree;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.TreeMap;
/*
Input:
30
/ \
10 60
/
59
/
58
/
55
/
50
Output: 50 55 58 59 60
*/
public class BottomViewOfBinaryTree {
private NodeForBottomView rootNode = null;
public static void main(String[] args) {
new BottomViewOfBinaryTree();
}
public BottomViewOfBinaryTree() {
addNode(rootNode, 30);
addNode(rootNode, 10);
addNode(rootNode, 60);
addNode(rootNode, 59);
addNode(rootNode, 58);
addNode(rootNode, 55);
addNode(rootNode, 50);
Map<Integer, NodeForBottomView> map = printBottomViewIteratively(rootNode);
for (Map.Entry<Integer, NodeForBottomView> element : map.entrySet()) {
System.out.print(element.getValue().getData() + " ");
}
System.out.println();
map = new TreeMap<>();
printBottomViewRecursively(rootNode, map, 0);
for (Map.Entry<Integer, NodeForBottomView> element : map.entrySet()) {
System.out.print(element.getValue().getData() + " ");
}
}
private Map<Integer, NodeForBottomView> printBottomViewIteratively(NodeForBottomView rootNode) {
if (rootNode == null)
return new TreeMap<>();
Map<Integer, NodeForBottomView> map = new TreeMap<>();
Queue<NodeForBottomView> queue = new LinkedList<>();
queue.add(rootNode);
while (!queue.isEmpty()) {
NodeForBottomView temp = queue.poll();
int currentLevel = temp.getLevel();
map.put(currentLevel, temp);
if (temp.getLeftNode() != null) {
temp.getLeftNode().setLevel(currentLevel - 1);
queue.add(temp.getLeftNode());
}
if (temp.getRightNode() != null) {
temp.getRightNode().setLevel(currentLevel + 1);
queue.add(temp.getRightNode());
}
}
return map;
}
private void printBottomViewRecursively(NodeForBottomView rootNode, Map<Integer, NodeForBottomView> map, int hd) {
if(rootNode==null){
return;
}
map.put(hd, rootNode);
printBottomViewRecursively(rootNode.getLeftNode(), map, hd-1);
printBottomViewRecursively(rootNode.getRightNode(), map, hd+1);
}
private void addNode(NodeForBottomView rootNode, int data) {
if (rootNode == null) {
NodeForBottomView temp = new NodeForBottomView(data);
this.rootNode = temp;
} else {
addNodeInProperPlace(rootNode, data);
}
}
private void addNodeInProperPlace(NodeForBottomView rootNode, int data) {
if (data > rootNode.getData()) {
if (rootNode.getRightNode() != null) {
addNode(rootNode.getRightNode(), data);
} else {
NodeForBottomView temp1 = new NodeForBottomView(data);
rootNode.setRightNode(temp1);
}
} else if (data < rootNode.getData()) {
if (rootNode.getLeftNode() != null) {
addNode(rootNode.getLeftNode(), data);
} else {
NodeForBottomView temp1 = new NodeForBottomView(data);
rootNode.setLeftNode(temp1);
}
}
}
}
NodeForBottomView.java
package com.javabypatel.tree;
public class NodeForBottomView {
private int data;
private NodeForBottomView leftNode;
private NodeForBottomView rightNode;
private int level;
public NodeForBottomView(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public NodeForBottomView getLeftNode() {
return leftNode;
}
public void setLeftNode(NodeForBottomView leftNode) {
this.leftNode = leftNode;
}
public NodeForBottomView getRightNode() {
return rightNode;
}
public void setRightNode(NodeForBottomView rightNode) {
this.rightNode = rightNode;
}
public int getLevel() {
return level;
}
public void setLevel(int level) {
this.level = level;
}
}
You may also like to see
Top Binary tree interview questions in Java
Print a Binary Tree in Vertical Order
Print Nodes in Top View of Binary Tree
Traverse a Binary Tree in Level Order Traversal
Find Kth SMALLEST element in BST(Binary Search Tree)
Check whether Binary Tree is foldable or not.
Check if two nodes are cousins in a Binary Tree.
Get Level/Height of node in binary tree
Print nodes at K distance from Leaf node in Binary tree.
Construct a Binary Tree from In-order and Post-order traversals.
Zig Zag Traversal of Binary Tree.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment