Bottom View of a Binary Tree

Problem Statement

The problem “Bottom View of a Binary Tree” states that you are given a binary tree and now you need to find the bottom view for the given tree. When we see a tree from the downward direction. The nodes which are visible to us is the bottom view of the binary tree.

Example

5 6 4 7

Approach

The approach is simple because we have already solved a problem that is similar to this. The problem Top view of a binary tree is similar to this where we had to print the nodes which are visible to us from the above direction. So how do we solve the problem?

We need to use the concept of horizontal distance here. Whenever we move in the left direction of a node, we subtract from the horizontal distance of the current node. Similarly, if we move in the right direction, we add 1 to horizontal distance. Once we are familiar with this concept. We will use a map to keep track of nodes at each of the horizontal distance. Then we will traverse the tree and whenever we find a node we update our map. We will keep the horizontal distance as key and the node as the value to the map. So using a level order traversal, keep calculating the horizontal distance and updating the map.

After all of these calculations, simply print the elements in the map. Because the most left node is with most negative horizontal distance and the rightmost node has the highest positive value.

C++ code to print Bottom View of a Binary Tree

#include <bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node *left, *right;
};

node* create(int data){
    node* tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

int main(){
    node *root = create(2);
    root->left = create(3);
    root->right = create(7);
    root->left->left = create(5);
    root->left->right = create(4);
    root->left->right->left = create(6);

    map<int,int> m;
    queue<pair<int,node*>> q;
    q.push(make_pair(0, root));
    m[0] = root->data;
    while(!q.empty()){
        pair<int, node*> now = q.front();
        q.pop();

        m[now.first] = now.second->data;
        if(now.second->left)
        q.push(make_pair(now.first - 1, now.second->left));
        if(now.second->right)
        q.push(make_pair(now.first + 1, now.second->right));
    }
    for(auto x: m)
        cout<<x.second<<" ";
}

5 6 4 7

Java code to print Bottom View of a Binary Tree

import java.util.*;

class node{
  int data;
  node left, right;
  int hd;
}

class Main{

  static node create(int data){
      node tmp = new node();
      tmp.data = data;
      tmp.left = tmp.right = null;
      tmp.hd = 0;
      return tmp;
  }

  public static void main(String[] args){
    node root = create(2);
      root.left = create(3);
      root.right = create(7);
      root.left.left = create(5);
      root.left.right = create(4);
      root.left.right.left = create(6);

      Map<Integer, Integer> m = new TreeMap<Integer, Integer>();
      Queue<node> q = new LinkedList<node>();
      q.add(root);
      m.put(root.hd, root.data);
      while(!q.isEmpty()){
          node now = q.remove();

          m.put(now.hd, now.data);
          if(now.left != null){
          	now.left.hd = now.hd - 1;
          	q.add(now.left);
          }
          if(now.right != null){
          	now.right.hd = now.hd + 1;
          	q.add(now.right);
          }
      }
      for(Map.Entry<Integer, Integer> entry : m.entrySet())
          System.out.print(entry.getValue()+" ");
  }
}

5 6 4 7

Complexity Analysis

Time Complexity

O(NlogN), because we have traversed the tree and have updated the values. Because we have used a map, insertion, deletion, and searching is done in O(logN) time.

Space Complexity

O(N), at most there can be (N+1)/2 in the last level. Thus the space complexity is linear.