Bottom View of Binary Tree
FREE
Problem Statement
We need to print the bottom view of binary tree, i.e., all the bottommost nodes from left to right in a binary tree.
The 3D projection of a binary tree will have different views from different angles. In our case, we'll print the bottom view of the binary tree.
It's better to visualize them with horizontal distance (like an x-axis). The root node will be located at the horizontal distance or hd 0. The left child will have hd-1 of its parent and the child will have hd+1 of its parent. The bottommost nodes at each horizontal distance will be present in our output.
Note: Let's also assume that each child node makes a 45-degree angle with its parent node.
Let's look at this simple example of what the bottom view really looks like.
The bottom view of this binary tree will be 7 9 13 11 6.
Example
Note: To avoid confusion, level and height are the same thing in our topic of discussion.
Now, we'll again assume the same above example because we haven't discussed the height which will be used in our algorithm.
In this case, we'll get the output as 7 9 13 11 6.
But how about a different scenario. What if there are two child nodes at the same level and horizontal distance?
Example Explanation
Just like the x-axis, the root node is present at the origin (with horizontal distance, say hd, being 0) and at height 0. The immediate child nodes of the root node will be at height 1 with the left child node having a horizontal distance of hd-1 and the right child node having a horizontal distance of hd+1.
And if there are two nodes present at the same height as well as horizontal distance, the bottom-most node will be the one that comes later while traversing from left to right.
Constraints
Although we are not making any assumptions for the input nodes because they are hard-coded, let us assume that:
Approach 1 - HashMap & Recursion
We discussed how horizontal distance as well as levels in the above example. What if we start traversing the parent nopde and then its left and right child nodes one by one. As we go down at each of the horizontal distance axis vertically, we'll keep on updating our bottommost nodes. In this case, we'll start with the parent node (which has horizontal distance, hd, 0) and then traverse through its left and right child nodes. Since we want only the bottom-most nodes at each horizontal distance, we'll traverse through every node until we reach the maximum height where we'll have all the bottommost nodes of the tree.
Technically, we'll need a TreeMap that stores and sorts the entries based on their keys.
At height 0 and hd 0, we'll store the parent node in the map with its hd being the key and an array as the value that contains both height and data of the node. We'll traverse through its left and right child nodes and update the TreeMap if there's already a key present in the map. It recursively goes on until we traverse each node in the tree.
Algorithm
- Create a hashmap/treemap that stores the horizontal distance as the key and an array containing the node's value and its height as the value of the map.
- We'll perform the preorder traversal on the binary tree. (We need to traverse the parent node before traversing its left and right child nodes. This can be performed with preorder traversal).
- If we reach a node having the horizontal distance that already exists as key in the map and a height greater than that of the previous node, we need to update this key with the new node and its height.
- Else, we'll put a new key (horizontal distance) with the current node's value and its height.
Eventually, we'll end up getting the bottom-most nodes of the binary tree.
Code Implementation
C++
Java
Python
Output
Time Complexity
Since we are visiting each node in the tree once, the time complexity will be: O(N * logN), where N is the number of nodes of the binary tree
Space Complexity
We have used a map in our code to store all the nodes of the tree. If there are N nodes in a tree, the space complexity will be: O(N), where N is the number of nodes
Approach 2 - Queue
Note: We're calling the horizontal distance as hd in this approach too.
We already know that the sole purpose of a queue is to have First-in-First-out (FIFO) sequence. So, we can insert the parent node first in the queue along with the horizontal distance (hd=0). Following it will be the insertion of its left and right child node with their horizontal distances, hd-1, and hd+1 respectively. If you look clearly, this is exacly like Breadth First Search (BFS) where each node is visited and then all its adjacent nodes will be added to the queue.
We need to maintain a TreeMap to contain the key-value pairs in the sorted order of keys.
Now, whether we just need to put the horizontal distance as the key and node's value(or data) as the value here. If it's a new horizontal distance, it will be simply inserted. Or if this horizontal distance already exists as a key, it will be updated with its value. This would go on until each of the keys has got the values of the bottom-most nodes.
Algorithm
- Create a class for the node of the Tree and a class Pair that comprises a node and its level.
- We'll begin with the parent node with a horizontal distance which will be inserted into a queue.
- We need to perform the level order traversal (also known as Breadth First Search).
- A TreeMap will be used to sort the entries according to their keys. The horizontal distance will be the key whereas the node's value will be the value of the keys in the map.
- Once we get a new horizontal distance, we'll insert it into the queue. Each of these nodes will have a node's value and horizontal distance (hd).
- If the horizontal distance already exists in the map, then it will be updated with the new node's value whose height is greater than that of its previous one.
Code Implementation
C++
Java
Python
Output
Time Complexity
Any comparison to insert, remove, and get an element in a TreeMap takes O(logN) time. So, for N nodes in a tree, it will be:
O(N * log N), where N is the number of nodes present in the binary tree
Space Complexity
Since we have used a map in our code, the space complexity will be: O(N), where N is the number of nodes
Conclusion
- The bottom view of a binary tree is the representation of all the bottommost nodes in a binary tree.
- We can simplify our understanding of bottommost nodes with the help of horizontal distances(hd) and the height of the successor in a binary tree.
- The bottom view of a binary tree can be found in two ways:
- HashMap and Recursion
- Queue
FAQs
Q: What is the Bottom View of a Binary Tree?
A: The bottom view of a binary tree refers to all the bottommost nodes of the binary tree. Similarly, there is a top, left, and right view of the binary tree.
Q: How can we Find the Bottom of a Binary Tree?
A: We've discussed two ways to find the bottom view of a binary tree:
- HashMap + Recursion, in which the preorder traversal takes place
- Queue, with the level order traversal (preorder traversal)