Bottom View of Binary Tree
Medium · Trees · Tree · Breadth-First Search · Hash Table · Binary Tree
Problem
Place the root of a binary tree at horizontal distance (column) 0. A left child sits one column to the left of its parent (-1), and a right child one column to the right (+1).
Looking at the tree from below, you see exactly one node in every column that has any nodes: the deepest node of that column. If two nodes share both the column and the depth, the one that comes later in level order (left to right within a level) is the one you see.
Return the values of the bottom view, from the leftmost column to the rightmost. An empty tree gives an empty list.
Examples
Input: root = [20,8,22,5,3,null,25,null,null,10,14] Output: [5,10,3,14,25]
10 hides 8 in column -1, 3 hides 20 in column 0, and 14 hides 22 in column 1.
Input: root = [1,2,3,null,4,5] Output: [2,5,3]
Nodes 4 and 5 are both in column 0 at depth 2. 5 comes later in level order, so it is the one seen; 1 is hidden above them.
Input: root = [] Output: []
No nodes, no view.
Constraints
- The number of nodes is in the range [0, 10^5]
- -10^4 <= Node.val <= 10^4
Approaches
- One level-order walk per column — time O(n · w), space O(n)
Follow-up
How would the top view differ? Keep the first node per column instead of the last: only set seen[col] when the column is new.
Related problems
Start free on Cariara · Coding problems · System design studio
