In this article, we see how to print the bottom view of Binary Tree. We discuss our approach to solve this problem and analyze the time and space complexities.
It is recommended to first learn Top View Of Binary Tree before proceeding with this problem. A lot of the implementation is based on the Top View Approach.
By Bottom View of Binary Tree, we mean the nodes visible when the tree is viewed from the bottom or from the leaves. A node is present in our bottom view it is the last node or the bottom-most node at it’s respective horizontal distance.
We calculate the horizontal distance of each node as follows:
- We fix the Horizontal Distance of Root of tree=0.
- Then, Horizontal Distance of Left Child=Horizontal Distance of it’s Parent Node – 1.
- Horizontal Distance of Right Child=Horizontal Distance of it’s Parent Node + 1.
Now let us look into an example. Consider this binary tree:
The Bottom View of this tree will be : 2 5 6 7.
Explanation
The nodes highlighted in the figure above represent the bottom view. We start from the root node 1 at level 1 the horizontal distance is fixed at 0, then we traverse each level and print the bottom-most node for that horizontal distance i.e. the node which comes last for a particular value of horizontal distance. At level 2 node 2 is the last node with horizontal distance -1 so print it. Node 5 at level 3 is the bottom-most node with horizontal distance 0. At the same level 3 node 6 is the bottom-most node with horizontal distance 3. At last level 4 node 7 has horizontal distance 2 so we print it.
Note: If one or more nodes have the same horizontal distance we consider the one’s which comes last during the level traversal.
For Example Node 1, Node 4 and Node 5 have same horizontal distance 0 but Node 5 comes later or last during level order traversal so we print node 5. Similar rule is followed for Node 3 and Node 7 having horizontal distance 2.
Input: hd=Horizontal distance
hd=0 20 -- level 1
/ \
/ \
hd= -1 10 30 -> hd= +1 -- level 2
/ \ / \
/ \ / \
hd= -2 5 15 25 35 -> hd= +2 -- level 3
hd=0 hd=0
// Tree is Viewed from the bottom here
Output: 5 10 25 30 35
Approach (Using Level Order Traversal and Hashing)
We follow these steps in order to implement this approach:
- The idea is to put the nodes with same horizontal distance(hd) together and order them on basis of their hd.
- We insert tree nodes along with their respective hd in a Queue during level order traversal by maintaining a pair class NodeObj.
- To ensure we get the bottom-most node or last node, maintain a Tree-Map of key-value pair (hd, Node-data) sorted on key hd. We keep updating and replacing the map’s key hd with the current node data until we traverse all nodes.
- For the first time, it will add a node’s hd to the map with it’s data as value, next time it will replace the value if next node’s hd is same. At the end, this make sure that the bottom-most node for that horizontal distance is present in the map.
- Then we just iterate through the Tree-Map values which will contains our Top View.
Note: We do not store node as the value in the Map only the node data is sufficient.
The Tree-Map for the above example looks like this:
| hd | Node-Data |
| -2 | 5 |
| -1 | 10 |
| 0 | 25 |
| +1 | 30 |
| +2 | 35 |
So let’s look at the code of the above approach in Java.
import java.util.Queue;
import java.util.TreeMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
// class to create a node
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}
class NodeObj // Each Object holds the current node to add in Queue
{
Node node;
int hd; // Horizontal Distance of each Node
NodeObj(Node node, int hd)
{
this.node = node;
this.hd = hd;
}
}
// class of binary tree
public class Tree
{
Node root;
// method to print the Bottom View of the binary tree
void bottomView(Node root)
{
if (root == null)
return; // There will be no Bottom View of a tree having root null
Queue<NodeObj> queue = new LinkedList<NodeObj>();
// Declare Map to maintain hd and node data.
Map<Integer,Integer> bottomView = new TreeMap<>();
// We first add the root into the queue along with it's hd 0.
queue.add(new NodeObj(root, 0));
// Standard level order traversal using Queue
while (!queue.isEmpty())
{
NodeObj curr = queue.poll(); // we dequeue the current NodeObj
Node tempNode=curr.node; // get the current node to process.
int hd=curr.hd; // get the node's respective horizontal distance.
// Every time we find a node having same horizontal distance
// we either replace the data in the map or add a new key hd.
bottomView.put(hd,tempNode.data);
// Now add the left and right child of each node
// to continue level order traversal
if (tempNode.left != null)
{
// hd of left child = hd of parent node - 1.
queue.add(new NodeObj(tempNode.left, hd - 1));
}
if (tempNode.right != null)
{
// hd of right child = hd of parent node + 1.
queue.add(new NodeObj(tempNode.right, hd + 1));
}
}
// We just print the values corresponding to each key(hd) or the nodes present in Bottom view
// This is the code to iterate over Map Values.
for (Entry<Integer, Integer> entry : bottomView.entrySet())
{
System.out.print(entry.getValue()+" ");
}
}
// Driver Code or Main method to test above functions
public static void main(String[] args)
{
Tree tree = new Tree();
tree.root = new Node(20);
tree.root.left = new Node(10);
tree.root.left.left = new Node(5);
tree.root.left.right = new Node(15);
tree.root.right = new Node(30);
tree.root.right.left = new Node(25);
tree.root.right.right = new Node(35);
System.out.println("The Bottom View of Binary Tree is: ");
System.out.println();
tree.bottomView(tree.root);
}
}
Output:
The Bottom View of Binary Tree is: 5 10 25 30 35
Time Complexity: On analyzing the time complexity of our approach we see the level order traversal of all the nodes require O(n) time. Along with this, each insertion in our Map takes O (log n) time. So the Overall time Complexity will be O (n*log n).
Space Complexity: We use a Queue that will store all the nodes present at all levels, the space required by our map would be less than our Queue so the overall space complexity will be O(n).
That’s it for the Bottom View of Binary tree you can try this approach and let us know in the comment section for any queries.
The post Bottom View of Binary Tree in Java appeared first on The Crazy Programmer.
from The Crazy Programmer https://ift.tt/3av49rf
Post a Comment