Bottom View of a Binary Tree
You are given a Binary Tree. We will suppose the left and right children of a node make an angle of 45 degrees with the parent node. You have to print the bottom view of the tree from left to right. Some points to keep in mind before approaching this question

Horizontal distances of:
 Root node to root node = 0.
 Right child to the root node = 1
 Left child to the root node = 1.
 If node n is the right child, then its distance from the root will be equal to the distance of its parent node +1.
 If node n is the left child, then its distance from the root will be equal to the distance of its parent node 1.
Let’s understand the problem statement with an example:
Example 1:
Output: 4 5 6 7
Explanation:
 The horizontal distance of the root node i.e. 1 is clearly 0.
 2 is the left child of 1, so its distance will be 01= 1
 2 is the right child of 1, so its distance will be 0+1= 1

Just like that, the horizontal distances of
 4 is 2
 5 is 0
 6 is 0
 7 is 2
Since at horizontal distance 0, there are two nodes, node 6 will be considered at the bottommost level, as it is more towards the right side. Therefore, if we see the bottommost nodes, what we get is 4 5 6 7
Approach 1: Using Queue
In this approach, we will be using a queue. We will traverse the Binary Tree in the level order fashion, insert the nodes in the queue. Level order traversal is iterating the tree in the order of breadth i.e, the first root node, then the children of the root node, etc We will be using the map to store the horizontal distance of each node.
Algorithm
 Create an ordered map and a queue. The horizontal distances of the nodes will be stored in the map while the queue will store the nodes according to level order traversing.
 Use the pair<> to store the root and the horizontal distance in the queue.
 Check if the queue is empty or not. If not, then:
 Create a variable ‘temp’ to store the front node of the queue and the horizontal distance of that node.
 Pop the front element.
 Iterate over and store the values of each key in a vector.
 The vector thus obtained will contain the bottom view node.
 Return the vector.
The implementation of the abovediscussed approach is:
CPP
#include<bits/stdc++.h> using namespace std; // Structure to create a node // having an integer value, data // and two pointers // to store the references of the // left and right children struct Node { int data; // variable to store horizontal // distance of a node int hd; Node *left, *right; Node(int key) { data = key; hd = INT_MAX; left = right = NULL; } }; // function that takes the node // of a tree as its parameter // and print the tree's bottom view. void BottomMostView(Node *root) { if (root == NULL) return; // variable to store horizontal // distance of a node. // initially set it to 0. int hd = 0; // a map to store the // pair of key and value map<int, int> m; // queue for storing the nodes of the tree, while // traversing the tree in level order. queue q; // set the horizontal distance of the root node // which is intialized to 0. root>hd = hd; // add the root to the queue. q.push(root); // traverse in a level order fashion // until queue becomes empty while (!q.empty()) { Node *temp = q.front(); q.pop(); // get the horizontal distance // of the node that is popped out // from the queue. hd = temp>hd; // the popped out node will be // placed in the map with // a key as its horizontal distance. m[hd] = temp>data; // add the left child of the popped out node, // into the queue, // with hd = hd  1 if (temp>left != NULL) { temp>left>hd = hd1; q.push(temp>left); } // add the right child of the popped out node, // into the queue, // with hd = hd + 1 if (temp>right != NULL) { temp>right>hd = hd+1; q.push(temp>right); } } // iterate over the nodes in the map. for (auto i = m.begin(); i != m.end(); ++i) cout << i>second << " "; } // Driver Code int main() { Node *root = new Node(1); root>left = new Node(2); root>right = new Node(3); root>right>left = new Node(5); root>right>right = new Node(6); root>right>left>left = new Node(7); root>right>left>right = new Node(8); BottomMostView(root); return 0; }
Output
7 5 8 6
JAVA
import java.util.*; import java.util.Map.Entry; // Class to create a node // having an integer value, data // and two pointers // to store the references of the // left and right children class Node { int data; // variable to store horizontal // distance of a node int hd; Node left, right; public Node(int key) { data = key; hd = Integer.MAX_VALUE; left = right = null; } } class Tree { Node root; // Default constructor public Tree() {} // Parameterized constructor public Tree(Node node) { root = node; } // method that takes the node // of a tree as its parameter // and print the tree's bottom view. public void BottomMostView() { if (root == null) return; // variable to store horizontal // distance of a node. // initially set it to 0 int hd = 0; // a map to store the // pair of key and value Map<Integer, Integer> map = new TreeMap<>(); // queue for storing the nodes of the tree, while // traversing the tree in level order. Queue queue = new LinkedList(); // set the horizontal distance of the root node // which is intialized to 0. root.hd = hd; // add the root to the queue. queue.add(root); // traverse in a level order fashion // until queue becomes empty while (!queue.isEmpty()) { Node temp = queue.remove(); // get the horizontal distance // of the node that is popped out // from the queue. hd = temp.hd; // the popped out node will be // placed in the map with // a key as its horizontal distance. map.put(hd, temp.data); // add the left child of the popped out node, // into the queue, // with hd = hd  1 if (temp.left != null) { temp.left.hd = hd1; queue.add(temp.left); } // add the left child of the popped out node, // into the queue, // with hd = hd + 1 if (temp.right != null) { temp.right.hd = hd+1; queue.add(temp.right); } } // map's values are extracted to a set // so that the iterator can iterate over it Set<Entry<Integer, Integer>> set = map.entrySet(); // Iterator to traverse over the set Iterator<Entry<Integer, Integer>> iterator = set.iterator(); // Traversing elements of the map with the iterator. while (iterator.hasNext()) { Map.Entry<Integer, Integer> me = iterator.next(); System.out.print(me.getValue()+" "); } } } // Main driver class public class BottomMostView { public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.right.left = new Node(5); root.right.right = new Node(6); root.right.left.left = new Node(7); root.right.left.right = new Node(8); Tree tree = new Tree(root); tree.BottomMostView(); } }
Output
7 5 8 6
Python
# Class to create a node # having an integer value, data # and two pointers # to store the references of the # left and right children class Node: def __init__(self, key): self.data = key self.hd = 1000000 self.left = None self.right = None # method that takes the node # of a tree as its parameter # and print the tree's bottom view. def BottomMostView(root): if (root == None): return # variable to store horizontal # distance of a node. # initially set it to 0 hd = 0 # a map to store the # pair of key and value m = dict() # queue for storing the nodes of the tree, while # traversing the tree in level order. q = [] # set the horizontal distance of the root node # which is intialized to 0. root.hd = hd # add the root to the queue. q.append(root) # traverse in a level order fashion # until queue becomes empty while (len(q) != 0): temp = q[0] q.pop(0) # get the horizontal distance # of the node that is popped out # from the queue. hd = temp.hd # the popped out node will be # placed in the map with # a key as its horizontal distance. m[hd] = temp.data # add the left child of the popped out node, # into the queue, # with hd = hd  1 if (temp.left != None): temp.left.hd = hd  1 q.append(temp.left) # add the left child of the popped out node, # into the queue, # with hd = hd + 1 if (temp.right != None): temp.right.hd = hd + 1 q.append(temp.right) # Traversing elements of the map with the iterator. for i in sorted(m.keys()): print(m[i], end = ' ') # Driver Code if __name__=='__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.right.left = Node(5) root.right.right = Node(6) root.right.left.left = Node(7) root.right.left.right = Node(8) BottomMostView(root)
Output
7 5 8 6
Complexity Analysis
Time Complexity : O(n*log(n)), where ‘n’ is the number of nodes in the binary tree. Since we are traversing all the nodes of the binary tree in level order traversing and we know that the complexity to insert in an ordered map is log n. Space Complexity: O(n), where ‘n’ is the number of nodes in the binary tree as the queue used in the approach is of the size n.
Approach 2: Using Recursion and Map
This is an optimized approach, with reduced time complexity. We will use both recursion and map in this approach. The map will be used to store a key which is the horizontal distances of the nodes and a pair<a, b> where a is the value of the node and b is the height of the node.
Algorithm
 Create a map that will be used to store a key, which is the horizontal distances, “hd” of the nodes and a pair<a, b> where a is the value of the node and b is the height of the node.
 The root node will be the starting point, so its horizontal distance and height, both will be 0, and the horizontal distances and heights of all other nodes will be computed with reference to the root node.
 If for some horizontal distance there is no node present, then insert it into the map
 Recursively find the bottommost node in the left subtree.
 Use recursion on the left subtree to find the height and horizontal distance. As it is the left child of the node, height will be height + 1, and its horizontal distance from the existing node will be the horizontal distance of the current node1
 Again Use recursion on the left subtree to find the height and horizontal distance. As it is the left child of the node, height will be height + 1, and its horizontal distance from the existing node will be the horizontal distance of the current node+1
 The vector thus obtained will contain all the bottom view nodes.
 Return the vector.
. The implementation of the abovediscussed approach is:
CPP
#include <bits/stdc++.h> #include <map> using namespace std; // Structure to create a node // having an integer value, data // and two pointers // to store the references of the // left and right children struct Node { // data of the node int data; // variable to store horizontal // distance of a node int hd; Node * left, * right; Node(int key) { data = key; hd = INT_MAX; left = right = NULL; } }; // Helper function to recursively // find a tree's bottom view. void findBottomViewUtil(Node * root, int curr, int hd, map <int, pair <int, int>> & m) { // Base case if (root == NULL) return; // if for some hd // there is no node present, // then insert it into the map if (m.find(hd) == m.end()) { m[hd] = make_pair(root > data, curr); } // case to handle the situation // having more than one nodes at a // certain hd else { pair < int, int > p = m[hd]; if (p.second <= curr) { m[hd].second = curr; m[hd].first = root > data; } } // recursively find bottommost node // in the left subtree findBottomViewUtil(root > left, curr + 1, hd  1, m); // recursively find bottommost node // in the right subtree findBottomViewUtil(root > right, curr + 1, hd + 1, m); } // function that takes the node // of a tree as its parameter // and print the tree's bottom view. void BottomMostView(Node * root) { // create a map // for storing the // hd, height and data of the nodes map < int, pair < int, int > > m; findBottomViewUtil(root, 0, 0, m); // the map containing the bottommost nodes // returned by the function // findBottomView() map < int, pair < int, int > > ::iterator it; for (it = m.begin(); it != m.end(); ++it) { pair < int, int > p = it > second; cout << p.first << " "; } } int main() { Node *root = new Node(1); root>left = new Node(2); root>right = new Node(3); root>right>left = new Node(5); root>right>right = new Node(6); root>right>left>left = new Node(7); root>right>left>right = new Node(8); BottomMostView(root); return 0; }
Output
7 5 8 6
JAVA
import java.io.*; import java.lang.*; import java.util.*; class Main{ // Class to create a node // having an integer value, data // and two pointers // to store the references of the // left and right children static class Node { int data; // variable to store horizontal // distance of a node int hd; Node left, right; public Node(int key) { data = key; hd = Integer.MAX_VALUE; left = right = null; } } // Helper method to recursively // find a tree's bottom view. static void findBottomViewUtil(Node root, int curr, int hd, TreeMap<Integer, int[]> m) { // Base case if (root == null) return; // if for some hd // there is no node present, // then insert it into the map if (!m.containsKey(hd)) { m.put(hd, new int[]{ root.data, curr }); } // case to handle the situation // having more than one nodes at a // certain hd else { int[] p = m.get(hd); if (p[1] <= curr) { p[1] = curr; p[0] = root.data; } m.put(hd, p); } // recursively find bottommost node // in the left subtree findBottomViewUtil(root.left, curr + 1, hd  1, m); // recursively find bottommost node // in the right subtree findBottomViewUtil(root.right, curr + 1, hd + 1, m); } // method that takes the node // of a tree as its parameter // and print the tree's bottom view. static void BottomMostView(Node root) { // create a map // for storing the // hd, height and data of the nodes TreeMap<Integer, int[]> m = new TreeMap<>(); findBottomViewUtil(root, 0, 0, m); // the map containing the bottommost nodes // returned by the function // findBottomView() for(int val[] : m.values()) { System.out.print(val[0] + " "); } } // Driver Code public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.right.left = new Node(5); root.right.right = new Node(6); root.right.left.left = new Node(7); root.right.left.right = new Node(8); BottomMostView(root); } }
Output
7 5 8 6
Python
# Class to create a node # having an integer value, data # and two pointers # to store the references of the # left and right children class Node: def __init__(self, key = None, left = None, right = None): self.data = key self.left = left self.right = right def BottomMostView(root): # create a dictionary # for storing the # hd, height and data of the nodes d = dict() findBottomViewUtil(root, d, 0, 0) # Iterate over the dictionary # to print the bottom most nodes of the tree for i in sorted(d.keys()): print(d[i][0], end = " ") def findBottomViewUtil(root, d, hd, level): # Base case if root is None: return # if for some hd # there is no node present, # then insert it into the dictionary if hd in d: if level >= d[hd][1]: d[hd] = [root.data, level] else: d[hd] = [root.data, level] # recursively find bottommost node # in the left subtree findBottomViewUtil(root.left, d, hd  1, level + 1) # recursively find bottommost node # in the right subtree findBottomViewUtil(root.right, d, hd + 1, level + 1) # Driver Code if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.right.left = Node(5) root.right.right = Node(6) root.right.left.left = Node(7) root.right.left.right = Node(8) BottomMostView(root)
Output
7 5 8 6
Complexity Analysis
Time Complexity : O(n), where ‘n’ is the number of nodes in the binary tree. Space Complexity: O(n), where ‘n’ is the number of nodes in the binary tree as in the worst case, a queue of the size n will be used.
Wrapping Up!
In this article, we have learned an amazing concept of Binary Trees. Binary Tree is one of the most important data structures and is usually asked in the top interview questions as well. “Bottom View of a Tree” is a popular as well as a very important problem that has been asked in various interview questions. In this article, we have included proper diagrams of trees for a better understanding for you. We also learned about what is levelorder traversal and how it will be beneficial over other traversals i.e., inorder traversal, preorder traversal, and postorder traversal in such kinds of problems. We also discussed two wellexplained approaches along with some suitable examples to solve this problem:
 Using Queue
 Using Recursion and Map
We also covered in detail how both of the approaches work and what is the significance of both of them respectively. Discussed their time complexity as well as space complexity along with a proper explanation. Different programmers prefer different languages for coding. So, we made sure that all our readers can refer to this article. That’s why, this article also contains wellexplained codes for both the approaches in the three most popular languages which are c++, Java, and python along with their respective outputs attached to the article for a better understanding of a wide range of our readers. We sincerely hope that this article has walked you through some deep and important concepts of Binary Trees and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article. Happy Learning!
People are also reading:
 Breadth First Search Graph: DSA
 What is Shell Sort?
 Circular Linked List
 Find minimum jumps required to reach the destination
 Data Structure & Algorithm: Interpolation Search
 DSA: Recursion
 Rod Cutting Problem – Dynamic Programming
 Construct a Binary Tree from Inorder and Preorder traversals
 Write a Program to convert given inches into equivalent yard, and feet
 Find the maximum product of two integers in an array
Leave a Comment on this Post