Problem Statement

Given root of binary tree, return the bottom view of the binary tree.

The bottom view of a binary tree is the set of nodes visible when the tree is viewed from the bottom. Return nodes from the leftmost node to the rightmost node. Also if 2 nodes are outside the shadow of the tree and are at the same position then consider the node that appears later in level traversal.

The bottom view of a binary tree is the set of nodes visible when the tree is observed from the bottom.

• For each horizontal distance (HD) from the root, include the last node encountered when traversing level by level (top to bottom).
• Nodes in the same vertical line are replaced by the nodes at deeper levels.

Examples

Example 1:

Input:
        1
       / \
      2   3
     / \   \
    4   5   6
Output: [4, 2, 5, 3, 6]

Explanation:
The horizontal distances for nodes are:
HD -2: Node 4
HD -1: Node 2
HD 0: Node 5
HD 1: Node 3
HD 2: Node 6
The bottommost nodes visible are [4, 2, 5, 3, 6].

Example 2:

Input:
         1
        / \
       2   3
        \
         4
          \
           5
            \
             6
Output: [2, 4, 5, 6]

Explanation:
The horizontal distances for nodes are:
HD -1: Node 2
HD 0: Node 4
HD 1: Node 5
HD 2: Node 6
The bottommost nodes visible are [2, 4, 5, 6].

Different Approaches

1️⃣ Horizontal Distance Approach

Intuition:

The bottom view of a binary tree consists of nodes visible when the tree is viewed from the bottom. For each horizontal distance (HD), the node appearing last (at the deepest level) is included in the view.

Key Observations:

1. Horizontal Distance (HD):
   • Start with HD = 0 for the root.
   • Move left → Decrease HD by 1.
   • Move right → Increase HD by 1.
2. Bottom View Selection:
   • Use level order traversal (BFS) to process nodes level by level.
   • Track the last node encountered at each HD using a map or similar data structure. This ensures deeper nodes replace shallower ones.

Approach:

1. Level Order Traversal (BFS):
   • Traverse the tree using a queue. Each node is paired with its HD.
   • For every node, update the map with its HD and value (this replaces any previously stored node for the same HD).
2. Track Bottom Nodes by HD:
   • Use a map to store the most recent (deepest) node encountered for each HD.
3. Extract Results:
   • Traverse the map in ascending order of HD to get the bottom view.

Code:

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

// Definition for a binary tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> bottomView(TreeNode* root) {
    if (!root) return {};

    // Map: HD -> Node value
    map<int, int> bottomNodes;
    // Queue for BFS: (node, HD)
    queue<pair<TreeNode*, int>> q;

    q.push({root, 0}); // Root has HD = 0

    while (!q.empty()) {
        auto [node, hd] = q.front();
        q.pop();

        // Update the map with the current node at this HD
        bottomNodes[hd] = node->val;

        // Traverse the left and right children
        if (node->left) {
            q.push({node->left, hd - 1});
        }
        if (node->right) {
            q.push({node->right, hd + 1});
        }
    }

    // Extract the bottom view from the map
    vector<int> result;
    for (auto& [hd, value] : bottomNodes) {
        result.push_back(value);
    }

    return result;
}

// Helper function for building tree (optional)
TreeNode* buildTree() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->left->right->right = new TreeNode(5);
    root->left->right->right->right = new TreeNode(6);
    return root;
}

// Main
int main() {
    TreeNode* root = buildTree();
    vector<int> result = bottomView(root);
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N log N)
  • Traversal: Each node is visited once during BFS. which takes O(N), where N is the  number of nodes.
  • Map Operations: Insertion into the map (HD→ node value) is O(log K), where K is the number of unique HDs. Since K ≤ N, this takes O(N log N).
  • Overall: O(N log N).
• Space Complexity: O(N)
  • Map Storage: Stores O(K) HD entries, where K≤N, it takes O(N).
  • Queue Storage: Stores up to O(N) nodes in the BFS queue O(N).
  • Overall O(N)