Bottom View of Binary Tree
The array root holds a binary tree: the root at index 0, the children of index i at 2i+1 (left) and 2i+2 (right), -1 for an empty spot, and possibly extra -1 entries at the end.
The root is in column 0; a left step moves one column left, a right step one column right. Seen from below, each column shows its deepest node, and on a tie the last one on that level read from left to right (the larger index). Return the values you see, leftmost column first.
Function
- rootinteger-array
- the tree in heap order, with -1 for an empty spot
- Returnsinteger-array
- the value seen from below in each column, leftmost column first
Constraints
1 ≤ root.length ≤ 32767- Each
root[i]is-1or a value with0 ≤ root[i] ≤ 104, and no value appears twice. root[0]is never-1, so the tree has at least one node.- The array may end with extra
-1entries past the last node. - Both children of an empty spot are empty too, and the tree has at most
14levels.
Examples
- Input
- root = [5, 2, 9, 4, 7, 1, 6]
- Output
- [4, 2, 1, 9, 6]
- Explanation
- Column 0 holds
5and, two levels down,7(index 4) and1(index 5).1comes later on the shared level, so it shows. Columns -2, -1, 1 and 2 hold4,2,9and6.
- Input
- root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
- Output
- [5, 4, 3]
- Explanation
- Column -1 holds
2and, two levels lower,5(index 9), so you see5. In column 0,4sits below the root. Column 1 holds only3.
- Input
- root = [8, -1, -1, -1]
- Output
- [8]
- Explanation
- Every spot after the root is
-1, so8is the only node and column 0 the only column.
Follow-up
If a tie on a column's deepest level should return every tied node, left to right, how would the breadth-first version change? What would column 0 of example 1 give?
Hints
Open them one at a time. Each one gives away a little more.
Number the columns: the root is 0, a left step subtracts 1 and a right step adds 1. Looking from below, which node of a column do you see, and what if two nodes of that column sit on the same level?
Visit the nodes level by level, left to right inside each level, and write each node's value into its column, replacing what was there. What is left in each column at the end?
Use a queue of (index, column) pairs and queue the left child before the right one. Overwrite the column's value for every node, track the smallest and largest column, and read the columns in order at the end.
Solution
Each column shows its deepest node, and a tie goes to the node later in level order. A breadth-first search visits nodes in level order, so the last node it visits in a column is the answer: let every node overwrite its column's slot.
Depth-first, deepest node per column
Intuition
Walk the tree depth-first, handing each node its column and depth, and keep, per column, the depth and value of the deepest node so far.
Visiting the left subtree before the right one meets the nodes of a level from left to right, so the node you want is the last one met: replace when the depth is greater or equal. In example 1 the walk meets 7 and then 1, both at depth 2 in column 0, and 1 takes the column.
The columns form one unbroken range, so track the smallest and largest and read every column between. One visit per node gives O(n) time, and the recursion is h calls deep for a tree of h levels.
Algorithm
- Visit the root with column 0 and depth 0.
- Skip index
iwhen it lies past the end of the array orroot[i]is-1. - If the column has no node yet, or this depth is greater than or equal to the stored one, store this depth and value.
- Visit
2i+1with columncol-1, then2i+2with columncol+1, both one level deeper. - Return the stored values, smallest column first.
def bottomView(root):
n = len(root)
best = {} # column -> (depth, value) of the deepest node found so far
def visit(i, col, depth):
if i >= n or root[i] == -1:
return
# Replace on a greater or equal depth: on a tie, the node
# met last is the one further right, which comes later in level order.
if col not in best or depth >= best[col][0]:
best[col] = (depth, root[i])
visit(2 * i + 1, col - 1, depth + 1)
visit(2 * i + 2, col + 1, depth + 1)
visit(0, 0, 0)
# The columns that hold a node form one unbroken range.
return [best[col][1] for col in range(min(best), max(best) + 1)]Breadth-first, last node per column
Intuition
A queue where each node that leaves appends its left child, then its right, hands nodes out in level order: every node of depth d before any of depth d+1, and each level from left to right. Among a column's nodes the deepest comes out last, and on a tie the one further right. So when every node overwrites its column's slot, each slot ends up holding the node seen from below, with no depth to compare.
In example 1, 7 writes column 0 and 1 overwrites it.
Each node costs one queue visit and one map write: O(n) time. The queue can hold a whole level, about half the nodes, so the space is O(n).
Algorithm
- Put the pair (index 0, column 0) in a queue.
- Take out a pair (
i,col) and storeroot[i]undercol, replacing any earlier value. - Add (
2i+1,col-1), then (2i+2,col+1), for each child that is inside the array and not-1. - Repeat until the queue is empty, tracking the smallest and largest column.
- Return the map's values, smallest column first.
from collections import deque
def bottomView(root):
n = len(root)
bottom = {} # column -> value of the last node seen in that column
queue = deque([(0, 0)]) # (node index, column); the root is never empty
while queue:
i, col = queue.popleft()
# The queue hands out deeper nodes later, and right after left
# on one level, so the last node to reach a column is the one seen from below.
bottom[col] = root[i]
left, right = 2 * i + 1, 2 * i + 2
if left < n and root[left] != -1:
queue.append((left, col - 1))
if right < n and root[right] != -1:
queue.append((right, col + 1))
# The columns that hold a node form one unbroken range.
return [bottom[col] for col in range(min(bottom), max(bottom) + 1)]
Pitfalls and edge cases
- Replacing only on a strictly greater depth in the depth-first version. Example 1 then keeps
7instead of1. - Keeping the first node a breadth-first search gives each column. That is the top view.
- Adding the right child to the queue before the left one. Each level then comes out right to left, and ties go to the wrong node.
- Taking the leaves as the answer. In example 1 the leaf
7is hidden by1, and in example 2 the node4has a child yet is the bottom of column 0. - Sorting the columns as text. As strings,
"-10"lands between"-1"and"-2".
Frequently asked questions3
What is the bottom view of a binary tree?
Give the root column 0, each left step one column less and each right step one more. The bottom view lists the deepest node of each column, from left to right. This problem breaks a depth tie by level order, keeping the later node.
What is the time complexity of the bottom view of a binary tree?
O(n) for n nodes: the breadth-first search handles every node once with one hash map write. An ordered map such as a tree map adds a log w factor for w columns.
What is the difference between the top view and the bottom view?
Both pick one node per column. The top view picks the shallowest node and the bottom view the deepest. In the breadth-first version the top view keeps the first value a column receives; the bottom view overwrites it each time.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def bottomView(root):
# Write code hereTest #1
Test #2
Test #3
Argument
root = [5, 2, 9, 4, 7, 1, 6]
Expected Output
[4, 2, 1, 9, 6]