Print bottom view of a binary tree
Given a binary tree, print the bottom view of it. Assume the left and right child of a node makes a 45–degree angle with the parent.
For example, the bottom view of the following tree is 7, 5, 8, 6:
We can easily solve this problem with the help of hashing. The idea is to create an empty map where each key represents the relative horizontal distance of the node from the root node, and the value in the map maintains a pair containing the node’s value and its level number. Then perform preorder traversal on the tree. Suppose the current node’s level is more than or equal to the maximum level seen so far for the same horizontal distance as the current node’s or current horizontal distance is seen for the first time. In that case, update the value and the level for the current horizontal distance in the map. For each node, recur for its left subtree by decreasing horizontal distance and increasing level by one, and recur for right subtree by increasing both level and horizontal distance by one.
The following figure shows the horizontal distance and level of each node in the above binary tree. The final values in the map will be:
-1 —> (7, 4)
0 —> (5, 3)
1 —> (8, 4)
2 —> (6, 3)
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <iostream> #include <map> using namespace std; // Data structure to store a binary tree node struct Node { int key; Node *left, *right; Node(int key) { this->key = key; this->left = this->right = nullptr; } }; // Recursive function to perform preorder traversal on the tree and fill the map. // Here, the node has `dist` horizontal distance from the tree's root, // and the `level` represents the node's level. void printBottom(Node* node, int dist, int level, auto &map) { // base case: empty tree if (node == nullptr) { return; } // if the current level is more than or equal to the maximum level seen so far // for the same horizontal distance or horizontal distance is seen for // the first time, update the map if (level >= map[dist].second) { // update value and level for the current distance map[dist] = { node->key, level }; } // recur for the left subtree by decreasing horizontal distance and // increasing level by 1 printBottom(node->left, dist - 1, level + 1, map); // recur for the right subtree by increasing both level and // horizontal distance by 1 printBottom(node->right, dist + 1, level + 1, map); } // Function to print the bottom view of a given binary tree void printBottom(Node* root) { // create an empty map where // key —> relative horizontal distance of the node from the root node, and // value —> pair containing the node's value and its level map<int, pair<int, int>> map; // perform preorder traversal on the tree and fill the map printBottom(root, 0, 0, map); // traverse the map and print the bottom view for (auto it: map) { cout << it.second.first << " "; } } int main() { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->right = new Node(4); 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); printBottom(root); return 0; } |
Output:
7 5 8 6
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
import java.util.Map; import java.util.TreeMap; // A class to store a binary tree node class Node { int key; Node left = null, right = null; Node(int key) { this.key = key; } } // A Pair class class Pair<U, V> { public final U first; // first field of a pair public final V second; // second field of a pair // Constructs a new Pair with specified values private Pair(U first, V second) { this.first = first; this.second = second; } // Factory method for creating a Typed Pair immutable instance public static <U, V> Pair <U, V> of(U a, V b) { // calls private constructor return new Pair<>(a, b); } } class Main { // Recursive function to perform preorder traversal on the tree and fill the map. // Here, the node has `dist` horizontal distance from the tree's root, // and the `level` represents the node's level. public static void printBottom(Node root, int dist, int level, Map<Integer, Pair<Integer, Integer>> map) { // base case: empty tree if (root == null) { return; } // if the current level is more than or equal to the maximum level seen so far // for the same horizontal distance or horizontal distance is seen for // the first time, update the map if (!map.containsKey(dist) || level >= map.get(dist).second) { // update value and level for the current distance map.put(dist, Pair.of(root.key, level)); } // recur for the left subtree by decreasing horizontal distance and // increasing level by 1 printBottom(root.left, dist - 1, level + 1, map); // recur for the right subtree by increasing both level and // horizontal distance by 1 printBottom(root.right, dist + 1, level + 1, map); } // Function to print the bottom view of a given binary tree public static void printBottom(Node root) { /* Create a `TreeMap` where key —> relative horizontal distance of the node from the root node, and value —> pair containing the node's value and its level */ Map<Integer, Pair<Integer, Integer>> map = new TreeMap<>(); // perform preorder traversal on the tree and fill the map printBottom(root, 0, 0, map); // traverse the `TreeMap` and print the bottom view for (Pair<Integer, Integer> it: map.values()) { System.out.print(it.first + " "); } } public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.right = new Node(4); 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); printBottom(root); } } |
Output:
7 5 8 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
# A class to store a binary tree node class Node: def __init__(self, key=None, left=None, right=None): self.key = key self.left = left self.right = right # Recursive function to perform preorder traversal on the tree and fill the map. # Here, the node has `dist` horizontal distance from the tree's root, # and the `level` represents the node's level. def printBottom(root, dist, level, d): # base case: empty tree if root is None: return # if the current level is more than or equal to the maximum level seen so far # for the same horizontal distance or horizontal distance is seen for # the first time, update the dictionary if dist not in d or level >= d[dist][1]: # update value and level for the current distance d[dist] = (root.key, level) # recur for the left subtree by decreasing horizontal distance and # increasing level by 1 printBottom(root.left, dist - 1, level + 1, d) # recur for the right subtree by increasing both level and # horizontal distance by 1 printBottom(root.right, dist + 1, level + 1, d) # Function to print the bottom view of a given binary tree def printBottomView(root): # create a dictionary where # key —> relative horizontal distance of the node from the root node, and # value —> pair containing the node's value and its level d = {} # perform preorder traversal on the tree and fill the dictionary printBottom(root, 0, 0, d) # traverse the dictionary in sorted order of their keys and # print the bottom view for key in sorted(d.keys()): print(d.get(key)[0], end=' ') if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.right = Node(4) root.right.left = Node(5) root.right.right = Node(6) root.right.left.left = Node(7) root.right.left.right = Node(8) printBottomView(root) |
Output:
7 5 8 6
The time complexity of the above solution is O(n.log(n)) and requires O(n) extra space, where n is the size of the binary tree.
Exercise:
1. Reduce time complexity to linear using std::unordered_map/HashMap.
2. Modify the solution to print the top view of a binary tree.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)