Bottom View of Binary Tree — Solution in Python, Java & C++
Bottom View of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Bottom View of Binary Tree is a medium coding problem on hash table, breadth-first search and trees, asked in Amazon, Flipkart and Walmart interviews.
- Difficulty: Medium
- Topics: Hash Table, Breadth-First Search, Trees
- Asked at: Amazon, Flipkart, Walmart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return its bottom view: the values you would see looking up at the tree from below, listed from the leftmost column to the rightmost.
The root is in column 0; a node's left child is one column to the left and its right child one column to the right. For each column, the visible node is the deepest one; if several nodes of a column share the greatest depth, the one that comes last in a left-to-right level-order traversal is visible.
Example 1
Input: root = [20,8,22,5,3,null,25,null,null,10,14]
Output: [5,10,3,14,25]
Explanation: Column 0 holds 20 and, lower down, 3. Column −1 holds 8 and 10, column 1 holds 22 and 14 — in each the lower node shows.
Example 2
Input: root = [1,2,3,4,5,6,7]
Output: [4,2,6,3,7]
Explanation: 5 and 6 share column 0 at the same depth; 6 comes later in level order, so it is the one seen.
Example 3
Input: root = [7]
Output: [7]
Explanation: A single node is its own bottom view.
Constraints
1 <= number of nodes <= 10^51 <= Node.val <= 10^5
Hints for Bottom View of Binary Tree
Hint 1
Number the columns: root 0, left child column − 1, right child column + 1.
Hint 2
In a level-order traversal, a later node is never shallower than an earlier one, and ties at the same depth go left to right.
Hint 3
So run a BFS carrying columns and simply overwrite each column's entry with every node you meet — the last write is the visible node.
How to solve Bottom View of Binary Tree
A breadth-first traversal meets nodes in non-decreasing depth, left to right within a depth. The last node recorded for a column is therefore its deepest, and among the deepest the last in level order — exactly the bottom-view rule.
Approach
- Run a BFS from the root carrying each node's column (left
c - 1, rightc + 1). - For every node, set
view[column] = node.val, overwriting what was there. - Track the smallest and largest column.
- Return
view[min], …, view[max].
Why it works
When BFS reaches a node, every node before it in the queue is at most as deep, and nodes of the same depth before it lie to its left in level order. Overwriting keeps the latest visit, which is the deepest node of the column and, among equals, the last in level order.
Complexity
- Time —
O(n) with an array indexed by column (O(n log n) with a sorted map) - Space —
O(n)
Pitfalls
- A depth-first traversal can reach a shallower node of a column after a deeper one; it needs explicit depth comparisons.
- For a tie at the same depth the later node in level order wins — the opposite of the top view's rule.
Reference solution
Python
from typing import List, Optional
def bottomView(root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
view = {}
queue = [(root, 0)]
head = 0
while head < len(queue):
node, col = queue[head]
head += 1
view[col] = node.val
if node.left:
queue.append((node.left, col - 1))
if node.right:
queue.append((node.right, col + 1))
return [view[c] for c in range(min(view), max(view) + 1)]Java
public static int[] bottomView(TreeNode root) {
if (root == null) return new int[0];
Map<Integer, Integer> view = new HashMap<>();
List<TreeNode> nodes = new ArrayList<>();
List<Integer> cols = new ArrayList<>();
nodes.add(root);
cols.add(0);
int lo = 0, hi = 0;
for (int h = 0; h < nodes.size(); h++) {
TreeNode node = nodes.get(h);
int col = cols.get(h);
view.put(col, node.val);
lo = Math.min(lo, col);
hi = Math.max(hi, col);
if (node.left != null) { nodes.add(node.left); cols.add(col - 1); }
if (node.right != null) { nodes.add(node.right); cols.add(col + 1); }
}
int[] out = new int[hi - lo + 1];
for (int c = lo; c <= hi; c++) out[c - lo] = view.get(c);
return out;
}C++
vector<int> bottomView(TreeNode* root) {
if (!root) return {};
map<int, int> view;
vector<pair<TreeNode*, int>> q = {{root, 0}};
for (size_t h = 0; h < q.size(); h++) {
TreeNode* node = q[h].first;
int col = q[h].second;
view[col] = node->val;
if (node->left) q.push_back({node->left, col - 1});
if (node->right) q.push_back({node->right, col + 1});
}
vector<int> out;
for (auto& kv : view) out.push_back(kv.second);
return out;
}JavaScript
var bottomView = function(root) {
if (root === null) return [];
var view = {}, lo = 0, hi = 0;
var nodes = [root], cols = [0], head = 0;
while (head < nodes.length) {
var node = nodes[head], col = cols[head];
head++;
view[col] = node.val;
if (col < lo) lo = col;
if (col > hi) hi = col;
if (node.left !== null) { nodes.push(node.left); cols.push(col - 1); }
if (node.right !== null) { nodes.push(node.right); cols.push(col + 1); }
}
var out = [];
for (var c = lo; c <= hi; c++) out.push(view[c]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets · Breadth-First Search (BFS)