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:
-10^9 <= node's value <= 10^9
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++
#include <bits/stdc++.h>
#include <map>
using namespace std;
//Create new nodes with the class Node
struct Node{
/* class Node contains:
->node's value
->horizontal distance (hd)
->left and right child node
*/
int val; //node's value
int hd; //horizontal distance
// Left and right child nodes
Node * left;
Node * right;
//Constructor
Node(int data){
val = data;
hd = INT_MAX;//hd will be updated later
left = NULL;
right = NULL;
}
};
void bottomViewHelper(Node * node, int height, int hd, map <int, pair <int, int>> & map){
//A base case that returns when there's no node
if (node == NULL)
return;
//If any node for the current horizontal distance already exists, and
// the current node's height is greater than that of previous one
//we'll update it with the current node's value and height
if (map.find(hd) == map.end()){
map[hd] = make_pair(node -> val, height);
}
else{
//when the horizontal distance is not present in the map,
//we'll simply add the current one
pair < int, int > p = map[hd];
//if height is greater
if (p.second <= height){
map[hd].first = node -> val; //putting new node's value
map[hd].second = height; //updating height
}
}
//Recursively call left child node
bottomViewHelper(node -> left, height + 1, hd - 1, map);
//Recursively call right child node
bottomViewHelper(node -> right, height + 1, hd + 1, map);
}
void bottomView(Node * root){
//Key -> horizontal distance,
//value -> {node's value, height}
map < int, pair < int, int > > m;
//Calling helper method
bottomViewHelper(root, 0, 0, m);
//Printing the bottom-most nodes of the binary tree
map < int, pair < int, int > > ::iterator iter;
for (iter = m.begin(); iter != m.end(); ++iter){
pair < int, int > p = iter -> second;
cout << p.first << " ";
}
}
int main(){
//Create a binary tree
Node * root = new Node(3);
root -> left = new Node(6);
root -> right = new Node(12);
root -> left -> left = new Node(5);
root -> left -> right = new Node(11);
root -> right -> left = new Node(7);
root -> right -> right = new Node(8);
root -> left -> right -> left = new Node(20);
root -> left -> right -> right = new Node(17);
cout << "The bottom view of the binary tree is: ";
bottomView(root);
return 0;
}
Java
import java.util.*;
class Main{
//Create new nodes with the class Node
static class Node
{
/* class Node contains:
->node's value
->horizontal distance (hd)
->left and right child node
*/
int val; //node's value
int hd; //horizontal distance
// Left and right child nodes
Node left;
Node right;
//Constructor
public Node(int val)
{
this.val = val;
this.hd = Integer.MAX_VALUE; //hd will be updated later
this.left = null;
this.right = null;
}
}
static void bottomViewHelper(Node node, int height, int hd, TreeMap<Integer, int[]> map)
{
//A base case that returns when there's no node
if(node == null) return;
//If any node for the current horizontal distance already exists, and
// the current node's height is greater than that of previous one
//we'll update it with the current node's value and height
if(map.containsKey(hd) == true)
{
int[] existing = map.get(hd);
//if height is greater
if(existing[1] <= height)
{
existing[0] = node.val; //putting new node's value
existing[1] = height; //updating height
}
map.put(hd, existing); //update and add to the map
}else
{
//when the horizontal distance is not present in the map,
//we'll simply add the current one
map.put(hd, new int[]{node.val, height}); //add to the map
}
//Recursively call left child node
bottomViewHelper(node.left, height+1, hd-1, map);
//Recursively call right child node
bottomViewHelper(node.right, height+1, hd+1, map);
}
static void bottomView(Node root)
{
//TreeMap
//Key -> horizontal distance,
//value -> {node's value, height}
TreeMap<Integer, int[]> map = new TreeMap<>();
//Calling helper method
bottomViewHelper(root, 0, 0, map);
//Printing the bottom-most nodes of the binary tree
for(int arrays[]: map.values())
{
System.out.print(arrays[0] + " ");
}
}
public static void main(String[] args)
{
//Create a binary tree
Node root = new Node(3);
root.left = new Node(6);
root.right = new Node(12);
root.left.left = new Node(5);
root.left.right = new Node(11);
root.right.left = new Node(7);
root.right.right = new Node(8);
root.left.right.left = new Node(20);
root.left.right.right = new Node(17);
System.out.print("The bottom view of the binary tree is: ");
bottomView(root);
}
}
Python
# View of Binary Tree
class Node:
#class Node contains:
#->node's value
#->horizontal distance (hd)
#->left and right child node
def __init__(self, val = None,
left = None,
right = None):
self.data = val #node's value
# Left and right child nodes
self.left = left
self.right = right
def bottomViewHelper(node, d, hd, height):
# A base case that returns when there's no node
if node is None:
return
# if horizontal distance is already present in the dictionary, then it should be updated with new node data & height
if hd in d:
if height >= d[hd][1]:
d[hd] = [node.data, height]
else: # else the new horizontal distance will be inserted in the dictionary with new node data & height
d[hd] = [node.data, height]
bottomViewHelper(node.left, d, hd - 1, height + 1)
bottomViewHelper(node.right, d, hd + 1, height + 1)
def bottomView(root):
# Creating a dictionary
# key -> horizontal distance
# value -> pair of node's value and height
d = dict()
bottomViewHelper(root, d, 0, 0)
for i in sorted(d.keys()):
print(d[i][0], end = " ")
if __name__ == '__main__':
# Create a binary tree
root = Node(3);
root.left = Node(6);
root.right = Node(12);
root.left.left = Node(5);
root.left.right = Node(11);
root.right.left = Node(7);
root.right.right = Node(8);
root.left.right.left = Node(20);
root.left.right.right = Node(17);
print("The bottom view of the binary tree is: ", end=" ")
bottomView(root)
Output
The bottom view of the binary tree is: 5 20 7 17 8
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++
#include<bits/stdc++.h>
using namespace std;
//Create new nodes with the class Node
struct Node{
/* class Node contains:
->node's value
->horizontal distance (hd)
->left and right child node
*/
int val; //node's value
int hd; //horizontal distance
// Left and right child nodes
Node *left;
Node *right;
// Constructor
Node(int data){
val = data;
hd = INT_MAX;
left = NULL;
right = NULL;
}
};
void bottomView(Node *root){
if (root == NULL)
return;
int hd = 0; //horizontal distance (initialized to 0)
map<int, int> mp;
///Creating queue of the type Node
queue<Node *> q;
root->hd = hd;
q.push(root); //adding root to the queue
while (!q.empty()){
Node *temp = q.front();
q.pop(); //remove element from the queue
hd = temp->hd;
//Inserts a new key or updates the existing key with the new value
mp[hd] = temp->val;
if (temp->left != NULL){
temp->left->hd = hd-1;
q.push(temp->left);
}
if (temp->right != NULL){
temp->right->hd = hd+1;
q.push(temp->right);
}
}
//Using iterator to iterate through the values of the treemap
for (auto i = mp.begin(); i != mp.end(); ++i)
cout << i->second << " ";
}
int main(){
//Create a binary tree
Node * root = new Node(3);
root -> left = new Node(6);
root -> right = new Node(12);
root -> left -> left = new Node(5);
root -> left -> right = new Node(11);
root -> right -> left = new Node(7);
root -> right -> right = new Node(8);
root -> left -> right -> left = new Node(20);
root -> left -> right -> right = new Node(17);
cout << "The bottom view of the binary tree is: ";
bottomView(root);
return 0;
}
Java
import java.util.*;
//Create new nodes with the class Node
class Node{
/* class Node contains:
->node's value
->left and right child node
*/
int val; //node's value
// Left and right child nodes
Node left;
Node right;
//Constructor
public Node(int data){
val = data;
left = null;
right = null;
}
}
public class Main{
//Creating a pair class for node, and
//horizontal distance (initialized to 0)
static class Pair{
Node node;
int hd = 0;
}
public static void bottomView(Node root){
//Creating queue of the type Pair
Queue<Pair> queue = new LinkedList<>();
Pair p = new Pair();
p.node = root;
p.hd = 0;
queue.add(p);
Map<Integer, Integer> map = new TreeMap<>();
while(queue.size() > 0){
Pair temp = queue.remove();
//Inserts a new key or updates the existing key with the new value
map.put(temp.hd, temp.node.val);
if(temp.node.left != null){
Pair lp = new Pair(); //lp-> left pair
lp.node = temp.node.left;
lp.hd = temp.hd - 1;
queue.add(lp);
}
if(temp.node.right != null){
Pair rp = new Pair(); //rp -> right pair
rp.node = temp.node.right;
rp.hd = temp.hd + 1;
queue.add(rp);
}
}
//Using iterator to iterate the values of the treemap
Iterator<Integer> itr = map.values().iterator();
while(itr.hasNext())
System.out.print(itr.next() + " ");
}
public static void main(String[] args){
//Create a binary tree
Node root = new Node(3);
root.left = new Node(6);
root.right = new Node(12);
root.left.left = new Node(5);
root.left.right = new Node(11);
root.right.left = new Node(7);
root.right.right = new Node(8);
root.left.right.left = new Node(20);
root.left.right.right = new Node(17);
System.out.print("The bottom view of the binary tree is: ");
bottomView(root);
}
}
Python
#Using deque to push and pop the elements
from collections import deque
#Create new nodes with the class Node
class Node:
def __init__(self, data):
# class Node contains:
# ->node's value
# ->horizontal distance (hd)
# ->left and right child node
self.val = data # node's value
self.hd = float('inf') # horizontal distance
# Left and right child nodes
self.left = None
self.right = None
# Bottom View method
def bottomView(root):
# A base case that returns when there's no node
if root is None:
return
hd = 0 # horizontal distance (initialized to 0)
# Store start and end for the range of all horizontal distances
# This doesn't require sorting
start, end = 0, 0
hd_dict = dict()
# Creating queue to store nodes
q = deque()
# Add root node with the horizontal distance (hd=0) to the queue
root.hd = hd
q.append(root)
while q:
temp = q.popleft()
# Extract the horizontal distance value
# from the dequeued tree node.
hd = temp.hd
# Updating the start and end for the range horizontal distance
start = min(start, hd)
end = max(end, hd)
# Inserts a new node or updates the existing node in the dictionary
hd_dict[hd] = temp.val
if temp.left:
temp.left.hd = hd - 1
q.append(temp.left)
if temp.right:
temp.right.hd = hd + 1
q.append(temp.right)
# Traverse the map from the start to the end
for i in range(start, end+1):
print(hd_dict[i], end = " ")
if __name__=='__main__':
# Create a binary tree
root = Node(3);
root.left = Node(6);
root.right = Node(12);
root.left.left = Node(5);
root.left.right = Node(11);
root.right.left = Node(7);
root.right.right = Node(8);
root.left.right.left = Node(20);
root.left.right.right = Node(17);
print("The bottom view of the binary tree is: ", end=" ")
bottomView(root)
Output
The bottom view of the binary tree is: 5 20 7 17 8
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)
