Bottom View of Binary Tree
Bottom View of Binary Tree is a GeeksforGeeks problem (Medium). Given the root of a binary tree, return the nodes you would see if you looked at the tree from below, listed from left to right.
- Give every node a horizontal distance: the root is at 0, a left child is one less than its parent, and a right child is one more.
- Nodes with the same horizontal distance form one vertical column. From below you see only the bottom-most node of each column.
- If two nodes are equally low in the same column, the one that comes later in level-order traversal is the one you see.
- Return one value per column, from the leftmost column to the rightmost.
- 1 <= number of nodes <= 10⁵
- 1 <= node value <= 10⁵
Intuition
From below, each vertical column shows only its lowest node. The column is easy to carry down the tree: the root is 0, a left step subtracts 1 and a right step adds 1.
For "lowest", let the traversal order do the work. Breadth-first search visits the tree level by level, top to bottom and left to right, so the last node it visits in any column is the deepest one there, and on a tie the later one in level order. Overwriting the column on every visit therefore leaves exactly the bottom node, with no depth comparison at all.
Any "view" of a tree (top, bottom, left, right) or vertical-order question starts by giving each node a coordinate, then keeping one node per coordinate. The traversal order decides which node wins: BFS naturally lets the lowest node write last. There is no bottom view of binary tree leetcode problem as such; the closest LeetCode relative is Vertical Order Traversal of a Binary Tree (987), which keeps every node in each column instead of one.
Approach
Before reading on: label every node of a small tree with its column number. Which node in each column is lowest? Then decide which traversal visits that node last in its column without you checking depths.
Queue each node with its column
Start a queue with (root, 0). The column travels with the node, so it is computed once, when the child is enqueued.
Overwrite the column on every visit
Pop (node, col) and set seen[col] = node.data, with no check. BFS visits shallower levels first, so a later write in the same column always comes from a node at least as low.
Enqueue the children one column over
Push (node.left, col - 1) and (node.right, col + 1) for the children that exist. Only real nodes go in the queue.
Read the columns from left to right
When the queue is empty, sort the column keys and output their values. A sorted map (std::map, TreeMap) does this for you. Tracking the smallest and largest column instead lets you fill an array and skip the sort.
Bottom View of Binary Tree solution in Python | C++ | Java
Common pitfalls
Writing only when the column is empty
if col not in seen:
seen[col] = node.dataseen[col] = node.data
Keeping the first node per column is the top-view rule. With BFS the first node in a column is the highest one, so this returns the top view.
Overwriting in a DFS without depths
def dfs(node, col):
if node:
seen[col] = node.data
dfs(node.left, col - 1)
dfs(node.right, col + 1)def dfs(node, col, depth):
if node:
if col not in best or depth >= best[col][0]:
best[col] = (depth, node.data)
dfs(node.left, col - 1, depth + 1)
dfs(node.right, col + 1, depth + 1)DFS finishes the whole left subtree before the right one, so a shallow right-side node can be written after a deeper left-side node in the same column and wrongly replace it. With depths stored, the write happens only when the node is at least as low.
Returning the map in insertion order
return list(seen.values())
return [seen[c] for c in sorted(seen)]
A Python dict (or a C++ unordered_map, Java HashMap) keeps the order columns were first reached, which follows BFS, not left to right. The answer must be ordered by column.
Edge cases
A left child's right child and a right child's left child share both column and depth. The problem says the later one in level order is seen; BFS pushes left before right, so the unconditional overwrite already keeps that one.
Complexity
sorted(seen) runs once over at most n column keys.Top view, bottom view and vertical order
All three use the same column numbers. They differ only in which nodes of a column they keep.
| Problem | Keeps per column | Write rule in BFS |
|---|---|---|
| Top view | the highest node | write only if the column is empty |
| Bottom view | the lowest node (later one on a tie) | overwrite every time |
| Vertical order traversal | every node, top to bottom | append to the column's list |
Bottom View of Binary Tree FAQ
What is the bottom view of a binary tree?
The nodes seen when looking at the tree from underneath. Each vertical column (nodes with the same horizontal distance from the root) contributes its lowest node, and the columns are listed left to right. When two nodes are equally low in a column, the later one in level order is the one shown.
How do you find the bottom view of binary tree using recursion?
Pass the depth along with the column and store (depth, value) per column. Replace the stored entry only when the new node's depth is greater than or equal to the stored one. The >= matters: among equally deep nodes, preorder reaches them left to right, the same order as level order, so the later one wins as required. Without the depth check the recursion gives wrong answers.
Can you walk through a bottom view of binary tree example?
Take root 20 with children 8 and 22, where 8 has children 5 and 3, 3 has children 10 and 14, and 22 has a right child 25. The columns from left to right hold 5; 8 and 10; 20 and 3; 22 and 14; and 25. The lowest of each gives the bottom view 5 10 3 14 25.