Objective: – Given a binary tree, print it in Bottom View of it.
What is Bottom View: Bottom view means when you look the tree from the bottom the nodes you will see will be called the bottom view of the tree. See the example below.
as you can see in the example above,8, 4, 9, 5, 3, 7 is the bottom view of the given binary tree.
Approach:
This Approach is quite similar to the – Print the Binary Tree in Vertical Order Path.
and Print The Top View of a Binary Tree. Just modified the code so that it will print only the last element it will encounter in the vertical order. That will be the bottom view.
How will you know that you are visiting the last node at every level(Vertically)?
- Take a variable called level, whenever you go left, do level++ AND whenever you go right do level–.
- With step above we have separated out the levels vertically.
-
level distribution - Now you need to store the elements of each level, so create a TreeMap and the (key,value) pair will be (level,element at that level).
- Now all we need to do the level order traversal and store only recent visited node at each level(vertically), this way you will be storing only the last element at each level.
- We will use simple queue technique for level order traversal or BFS.
- we will create a class QueuePack, this will store the objects containing node and its level.
- At the end traverse through TreeMap and print all the values in it, it will be the bottom view of a tree.
- See the code for better understanding.
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.LinkedList; | |
| import java.util.Queue; | |
| import java.util.Set; | |
| import java.util.TreeMap; | |
| public class BottomViewOfBT { | |
| public static TreeMap<Integer, Integer> ht = new TreeMap<>();; | |
| public static void bottomView(Node root, int level) { | |
| if (root == null) | |
| return; | |
| // create a queue for level order traversal | |
| Queue<QueuePack> queue = new LinkedList<>(); | |
| // add root with level 0 (create a queue item pack) | |
| queue.add(new QueuePack(level, root)); | |
| while (!queue.isEmpty()) { | |
| QueuePack q = queue.remove(); | |
| // take out the items from the package | |
| Node tnode = q.tnode; | |
| int lvl = q.level; | |
| // keep updating the Map so that it will have the last entry from | |
| // each level(vertically) and that will the bottom view of the tree | |
| ht.put(lvl, tnode.data); | |
| // add the left and right children of visiting nodes to the queue | |
| if (tnode.left != null) { | |
| queue.add(new QueuePack(lvl – 1, tnode.left)); | |
| } | |
| if (tnode.right != null) { | |
| queue.add(new QueuePack(lvl + 1, tnode.right)); | |
| } | |
| } | |
| } | |
| public static void display() { // print the bottom view. | |
| Set<Integer> keys = ht.keySet(); | |
| for (Integer key : keys) { | |
| System.out.print(ht.get(key) + " "); | |
| } | |
| } | |
| public static void main(String[] args) { | |
| Node root = new Node(1); | |
| root.left = new Node(2); | |
| root.right = new Node(3); | |
| root.left.left = new Node(4); | |
| root.left.right = new Node(5); | |
| root.left.right.left = new Node(6); | |
| root.left.right.right = new Node(7); | |
| root.right.right = new Node(8); | |
| // root.right.right.left = new Node(30); | |
| bottomView(root, 0); | |
| display(); | |
| } | |
| } | |
| class Node { | |
| int data; | |
| Node left; | |
| Node right; | |
| public Node(int data) { | |
| this.data = data; | |
| left = null; | |
| right = null; | |
| } | |
| } | |
| // this class' represents the items stored in queue (used for level order | |
| // traversal). Objects will store the nodes and its level | |
| class QueuePack { | |
| int level; | |
| Node tnode; | |
| public QueuePack(int level, Node tnode) { | |
| this.level = level; | |
| this.tnode = tnode; | |
| } | |
| } |
Output: 4 6 5 7 8
how would the tpre-order traverse guarantee most recent visited node would be at “bottom” of a vertical level?
Would following sequence work?
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.left.right.left = new Node(6);
root.left.right.right = new Node(7);
root.left.right.right.right = new Node(9); ==> add another right node, which will be at same vertical level of node(8) but lower.
root.right.right = new Node(8);
We should get 4 6 5 7 9 as bottom view, but my guess is the code will return 4 6 5 7 8 (wrong result)
Hi Xiaozhen,
Code is correct and will return 4 6 5 7 9, don’t concentrate on preorder traversal, we are storing the node at each vertical level in a hash map ( in fact we are updating it so hash map will contain the last node visited at that level) See the diagram.
Code here: http://waytocrack.com/blog/bottom-view-of-binary-tree/
Can you please explain how 5 and 6 both being at level -0 are printed using the code ?
Print In-Order nodes where either left or right child is NULL
private static void printBottomView(Tree tree) {
if(tree==null)
return;
printBottomView(tree.leftChild);
if(tree.leftChild==null||tree.rightChild==null)
System.out.println(“===”+tree.data+”===”);
printBottomView(tree.rightChild);
}
The diagram shows doing Level +1, while going left, but in code, its doing Level-1, while traversing left. Can you please explain