Bottom View of Binary Tree

Given a binary tree, return an array where elements represent the bottom view of the binary tree from left to right.

Note: If there are multiple bottom-most nodes for a horizontal distance from the root, then the latter one in the level traversal is considered. For example, in the below diagram, 3 and 4 are both the bottommost nodes at a horizontal distance of 0, here 4 will be considered.

                      20
                    /    \
                  8       22
                /   \     /   \
              5      3 4     25
                     /    \      
                 10       14

For the above tree, the output should be 5 10 4 14 25.

Examples :

Input:
       1
     /   \
    3     2
Output: 3 1 2
Explanation: First case represents a tree with 3 nodes and 2 edges where root is 1, left child of 1 is 3 and right child of 1 is 2.

Thus bottom view of the binary tree will be 3 1 2.

Input:
         10
       /    \
      20    30
     /  \
    40   60
Output: 40 20 60 30

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Constraints:
1 <= Number of nodes <= 10⁵
1 <= Data of a node <= 10⁵

Approach 01:

#include <vector>
#include <map>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> bottomView(Node* root) {
        vector<int> result; // To store the bottom view of the tree
        if (root == NULL) {
            return result;
        }

        map<int, int> horizontalDistanceMap; // To store the bottom-most node's value for each horizontal distance
        queue<pair<Node*, int>> nodeQueue; // To perform level-order traversal
        nodeQueue.push({root, 0}); // Start with the root node at horizontal distance 0

        while (!nodeQueue.empty()) {
            pair<Node*, int> temp = nodeQueue.front();
            nodeQueue.pop();

            Node* currentNode = temp.first;
            int horizontalDistance = temp.second;

            // Update the bottom view map with the current node's value at the given horizontal distance
            horizontalDistanceMap[horizontalDistance] = currentNode->data;

            // Traverse the left subtree
            if (currentNode->left) {
                nodeQueue.push({currentNode->left, horizontalDistance - 1});
            }

            // Traverse the right subtree
            if (currentNode->right) {
                nodeQueue.push({currentNode->right, horizontalDistance + 1});
            }
        }

        // Collect the bottom view nodes from the map
        for (auto it : horizontalDistanceMap) {
            result.push_back(it.second);
        }

        return result;
    }
};

from collections import deque

class Solution:
    def bottomView(self, root):
        result = []  # To store the bottom view of the tree
        if root is None:
            return result

        horizontalDistanceMap = {}  # To store the bottom-most node's value for each horizontal distance
        nodeQueue = deque([(root, 0)])  # To perform level-order traversal, starting with the root at horizontal distance 0

        while nodeQueue:
            temp = nodeQueue.popleft()
            currentNode, horizontalDistance = temp

            # Update the bottom view map with the current node's value at the given horizontal distance
            horizontalDistanceMap[horizontalDistance] = currentNode.data

            # Traverse the left subtree
            if currentNode.left:
                nodeQueue.append((currentNode.left, horizontalDistance - 1))

            # Traverse the right subtree
            if currentNode.right:
                nodeQueue.append((currentNode.right, horizontalDistance + 1))

        # Collect the bottom view nodes from the map, sorted by horizontal distance
        for key in sorted(horizontalDistanceMap.keys()):
            result.append(horizontalDistanceMap[key])

        return result

Time Complexity

• Level-Order Traversal:

  The function uses a queue to perform a level-order traversal of the binary tree, which takes \( O(n) \) time, where \( n \) is the number of nodes in the tree.

• Updating Horizontal Distance Map:

  Each node’s horizontal distance and value are updated in a map. Since updating and accessing elements in a map (red-black tree) takes \( O(\log n) \) time, the overall time complexity for this part is \( O(n \log n) \).

• Collecting Results:

  Finally, we iterate through the map to collect the results, which takes \( O(n) \) time.

• Overall Time Complexity:

  Combining these steps, the overall time complexity is \( O(n \log n) \).

Space Complexity

• Auxiliary Space:

  The space complexity for storing the map is \( O(n) \) since, in the worst case, we store one entry for each node.

• Queue Space:

  The space complexity for the queue used in level-order traversal is \( O(n) \) in the worst case when all nodes are in the queue.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \).