Bottom View of Binary Tree
Given a binary tree, return its bottom view: the nodes visible when you look at the tree from below, listed from the leftmost to the rightmost horizontal position.
If several nodes share a horizontal position, the lowest one is visible. If two nodes are at the same position and the same depth, the one that comes later in level order (the right one) is taken.
Intuition
1 12 / \3 2 34 / \ \5 4 5 6Using horizontal distance (root 0, left child hd - 1, right child hd + 1), the bottom view here is 4, 2, 5, 3, 6. At hd 0, node 5 is deeper than node 1, so node 5 is the visible one.
This is the top view with the opposite rule: for each hd we want the last node seen in top-down order instead of the first. Level order visits deeper nodes later, so simply keep overwriting the value for that hd.
Approach: BFS, Overwrite per Horizontal Distance
- Queue of
(node, hd)pairs, starting with(root, 0). - Keep a sorted map from hd to value.
- Pop a pair and always set
map[hd] = node.value, replacing whatever was there. - Push
(left, hd - 1)and(right, hd + 1). - Read the map in increasing hd order.
The only difference from the top view is overwrite instead of insert-if-absent. Because BFS goes level by level and left to right, the final value at each hd is the lowest node, and for ties the rightmost one.
Code
class Solution {public:vector<int> bottomView(Node* root) {vector<int> ans;if (root == nullptr) return ans;map<int, int> bottom;queue<pair<Node*, int>> q;q.push({root, 0});while (!q.empty()) {Node* node = q.front().first;int hd = q.front().second;q.pop();bottom[hd] = node->data;if (node->left != nullptr) q.push({node->left, hd - 1});if (node->right != nullptr) q.push({node->right, hd + 1});}for (auto& entry : bottom) ans.push_back(entry.second);return ans;}};
Complexity
BFS visits each node once. The sorted map adds a log factor (it is O(n) with a hash map plus tracking the min and max hd).
The queue and the map hold up to O(n) entries.