On this page

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 1
2 / \
3 2 3
4 / \ \
5 4 5 6

Using 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

  1. Queue of (node, hd) pairs, starting with (root, 0).
  2. Keep a sorted map from hd to value.
  3. Pop a pair and always set map[hd] = node.value, replacing whatever was there.
  4. Push (left, hd - 1) and (right, hd + 1).
  5. 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

Time: O(n log n)

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).

Space: O(n)

The queue and the map hold up to O(n) entries.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"Bottom view is the mirror of top view. I use the same horizontal distance idea and the same BFS with a queue of node and distance pairs. The difference is the rule: for each distance I want the last node seen, not the first. Because level order visits deeper nodes later, I just overwrite the map entry every time, so what remains at each distance is the lowest node, and the rightmost one when depths tie. I then read the map from the smallest distance to the largest. Time is O of n log n with a sorted map, and space is O of n."
Next TopicBinary Tree Right Side View