?? Bottom View of Binary Tree

The task is to print the bottom view of binary tree. Bottom view of a binary tree is the set of nodes visible when the tree is viewed from the bottom.

Approach:

To solve the problem, we use a level order traversal (breadth-first search) combined with tracking the horizontal distance for each node. The key steps are:

1. Assign a horizontal distance (HD) to each node, starting from 0 for the root. Move left: Decrease HD by 1.Move right: Increase HD by 1.
2. Use a map to store the node that appears last at each horizontal distance.
3. Perform a level order traversal using a queue to process nodes level by level.
4. For each node: Update the map with the node data for its corresponding HD. Enqueue its left and right children with their respective HDs.
5. After the traversal, the map will contain the bottom-most node for each horizontal distance.
6. Finally, extract the map's values in sorted order of HD to get the bottom view.

Steps:

1. Queue for BFS: We perform a level-order traversal using a queue to ensure nodes are processed from top to bottom. Each node is associated with a horizontal distance.
2. Map for Horizontal Distance: The map tracks the bottom-most node for each horizontal distance. When a node at the same horizontal distance is encountered, the node at the lower level (or the latest one seen) is stored in the map.
3. Traversal: As we traverse the tree, we update the map, ensuring that only the bottom-most nodes are recorded for each horizontal distance.
4. Result: After the traversal, we extract the nodes from the map in order of horizontal distance, giving the bottom view.

?? View Full Code??

vector <int> bottomView(Node *root) {
        
     vector<int>ans;
        
     if(root == NULL){
        return ans;
     }
        
     map<int,int>topNode;
     queue<pair<Node*, int>>q;
        
     q.push(make_pair(root, 0));
        
     while(!q.empty()){
            
          pair<Node*, int>temp = q.front();
          q.pop();
             
          Node* frontNode = temp.first;
          int hd = temp.second;
            
          topNode[hd] = frontNode->data;
            
          if(frontNode->left){
              q.push(make_pair(frontNode->left, hd-1));
          }
          if(frontNode->right){
              q.push(make_pair(frontNode->right, hd+1));
          }
       }
       for(auto i:topNode){
           ans.push_back(i.second);
       }
       return ans;
    }        

Time Complexity: O(N)

Space Complexity: O(N)

?? GitHub Repository ??