Bottom View of Binary Tree

Bottom View of Binary Tree

Given a binary tree of integers. The task is to return an array of integers representing the bottom view of the Binary tree.

Bottom view of a Binary Tree: is a set of nodes visible when the tree is visited from the bottom.

Examples:
Input:

Output: [8, 4, 9, 5, 3, 7]
Explanation:

Input:

Output: [1, 3, 2]


Hashmap and Recursion Approach

The bottom view of a binary tree refers to the bottommost nodes present at the same level.

Algorithm

  • Perform a preorder traversal to calculate the level of each node of the binary tree.
  • Consider a hashmap and store the height into the map, where the key is the level or the horizontal distance of the ith node and the value is a pair (p, q), where p is the value of the node and q is the height of the node.
  • For every node:
    • Add the node to the resultant map if it is the first node to have the current horizontal distance.
    • Else, if a node is already present for the particular distance, replace the previous node with the current node, if the node has a height greater than the previous node.

C++ Code

void bottomview(Tree * root, map<int,vector<int>>& m, int lev, int h_dist){
 if (root == NULL)
   return;
 
 if (m.find(h_dist) == m.end()) {  
   m[h_dist].push_back(lev);
   m[h_dist].push_back(root -> data);
 }
  else {
   if (m[h_dist][0] <= lev) {
     m[h_dist][0] = lev;
     m[h_dist][1]= root -> data;
   }
 }
 // Calling the function for the right and left subtrees
 // with the appropriate parameters.
 bottomview(root -> left, m, lev + 1, h_dist - 1);
 bottomview(root -> right, m, lev + 1, h_dist + 1);
}
Void print_bottom_of_binary_tree(Tree* root){
   map<int,vector<int>> Map;
   bottomview(root, Map, 1, 0);
   for (auto it = Map.begin(); it != Map.end(); ++it)
   {
     cout << (it-> second)[1]<< " ";
   }
}

Java Code

bottomview(Node root, TreeMap<Integer, int[]> m, int curr, int hd)
{
    if (root == null)
        return;
 
     if (!m.containsKey(hd))
    {
        m.put(hd, new int[]{ root.data, curr });
    }
    else
    {
        int[] p = m.get(hd);
        if (p[1] <= curr)
        {
            p[1] = curr;
            p[0] = root.data;
        }
        m.put(hd, p);
    }
    printBottomViewUtil(root.left, curr + 1, hd - 1, m);
    printBottomViewUtil(root.right, curr + 1,hd + 1, m);
}
 
print_bottom_of_binary_tree(Node root)
{
    TreeMap<Integer, int[]> m = new TreeMap<>();
 
    printBottomViewUtil(root, 0, 0, m);
    for(int val[] : m.values())
    {
        System.out.print(val[0] + " ");
    }
}

Python Code

def print_bottom_of_binary_tree(root):   
      d = dict()
     
      printBottomViewUtil(root, d, 0, 0)
      for i in sorted(d.keys()):
        print(d[i][0], end = " ")
 
def bottomview(root, d, hd, level):
     if root is None:
        return
   
    if hd in d:
        if level >= d[hd][1]:
            d[hd] = [root.data, level]
    else:
        d[hd] = [root.data, level]
         
    bottomview(root.left, d, hd - 1,level + 1)
    bottomview(root.right, d, hd + 1,level + 1)

Time Complexity: O(N) where N is the number of nodes of the binary tree.
Space Complexity: O(N), as a map is used.


Queue Approach

The approach is to perform a level order traversal of the given binary tree and store them in a queue. Also, consider a map, which stores the horizontal distance of the nodes from root as the key.

Algorithm

  • Initialise a queue to store the nodes on performing level order traversal.
  • Push the root of the binary tree into the queue along with its horizontal distance(hd), which is 0.
  • Keep on pushing the left child to the queue along with their horizontal distance as hd – 1 and right child  as hd + 1.
  • While the queue is not empty, perform the following operations:
    • Store the front element of the queue is a variable, say, res.
    • Pop the element.
    • Put the dequeued element, stored in res and update its value in the map.
    • If a left child is present, push the left child into the queue along with its horizontal distance as hd – 1.
    • If a right child is present, push the right child into the queue along with its horizontal distance as hd + 1.
  • Print the values in the map which contains the bottom key of the binary tree.

C++ Implementation of Queue Method

void bottomview(Tree * root){
    int horizontalDistance = 0;
    map<int, Tree*> mp;
    queue<pair<Tree*, int>> q;
    q.push({root, 0});
    while (!q.empty()) {
        pair<BinaryTreeNode<int> *, int> p = q.front();
        q.pop();
        mp[p.second] = p.first;
        if (p.first->left != NULL) {
            q.push({p.first->left, p.second - 1});
        }
        if (p.first->right != NULL) {
            q.push({p.first->right, p.second + 1});
        }
    }
     
   for (auto i = mp.begin(); i != mp.end(); i++) {
        cout <<(i->second->data) <<” “;
    }
}

Java Implementation of Queue Method

class Pair {
	Tree root;
	int level;
	Pair() {
	}
	Pair(Tree root, int level) {
		this.root = root;
		this.level = level;
	}
}
 
bottomView(BinaryTreeNode root) {
		int horizontalDistance = 0;
		ArrayList<Integer> ans = new ArrayList<>();
		HashMap<Integer, BinaryTreeNode> mp = new HashMap<>();
 
		Queue<Pair> q = new LinkedList<>();
		Pair p1 = new Pair(root, 0);
		q.add(p1);
		while (!q.isEmpty()) {
			Pair p = q.poll();
			mp.put(p.level, p.root);
			if (p.root.left != null) {
				q.add(new Pair(p.root.left, p.level - 1));
			}
			if (p.root.right != null) {
				q.add(new Pair(p.root.right, p.level + 1));
			}
		}
		ArrayList<Integer> bottomView = new ArrayList<>();
 
		for (int key : mp.keySet()) {
			bottomView.add(key);
		}
		Collections.sort(bottomView);
		for (int i : bottomView) {
			System.out.print(mp.get(i).val + “ “);
		}
	}
}

Python Implementation of Queue Method

class Pair:
    
    def __init__(self, root, level):
        self.root = root
        self.level = level
        
	
def bottomView(root):
    horizontalDistance = 0
    mp = OrderedDict()
    
    q = []
    
    p1 = Pair(root, 0)
    q.append(p1)
    
    while len(q) > 0:
        p = q.pop(0)
        
        mp[p.level] = p.root
        
        if p.root.left is not None:
            q.append(Pair(p.root.left, p.level - 1))
            
        if p.root.right is not None:
            q.append(Pair(p.root.right, p.level + 1))
            
    bottomViewList = []
    
    for key in mp.keys():
        bottomViewList.append(key)
        
        
    bottomViewList.sort()
    
    for i in bottomViewList:
        print(mp.get(i).data, end = “ ”)

Time Complexity: O(N * log N) where N is the number of nodes of the binary tree.
Space Complexity: O(N), as a map is used.


Practice Questions

Vertical Order traversal of Binary Tree
Right view of Binary tree


Frequently Asked Questions

What is the left view of a binary tree?
The set of nodes visible when the tree is visited from the left is the left view of the binary tree.

How do you print the bottom of a binary tree?
The bottom view of a binary tree can be printed by hashing and level order traversal of the binary tree.

What is the diameter of a binary tree?
The diameter of a tree is the number of nodes on the longest path between two leaves in the tree

Additional Resources

Previous Post

Spring vs Spring Boot: Know The Difference

Next Post

Rearrange Array Alternately

Exit mobile version