What You See Looking Up at the Tree
Solve this ProblemYou are given the root of a binary tree. Give each node a column: the root is in column 0, a left child is one column to the left of its parent and a right child one column to the right. Looking up at the tree from below, in each column you see only the node nearest to the bottom; if two nodes are equally low in a column, you see the one that comes later in level order. Return the visible values from the leftmost column to the rightmost.
Since a breadth-first walk delivers nodes from the top row down, simply overwriting a column every time a node arrives leaves the bottom-most (and right-most) node in place.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; −100 ≤ node.val ≤ 100 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
Give each node a column: the root is column 0, a left child is one column to the LEFT of its parent (column − 1), a right child one column to the RIGHT (column + 1). Each node also has a row (its depth) - ◆
Looking up from below, in each column you see only the node closest to the bottom (largest row). If two nodes tie for that (same row, same column), the one that comes LATER in level order (the more rightward) is seen. Return the visible values from the leftmost column to the rightmost. An empty tree gives an empty list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Depth-First, Track the Deepest Node per Column
GoodWalk the tree depth-first while tracking each node's row and column. Keep, for every column, the (row, value) of the deepest node seen so far, and replace it whenever a node with a row greater than OR EQUAL to the stored one arrives (the "equal" case is the tie rule: a later node in the same row is more to the right, and the right one must win). A depth-first walk visits columns in no particular order of rows, so it compares rows for every node. At the end, read the columns from left to right.
O(n log n)O(n)1class Solution {
2 public List<Integer> bottomEdgeView(TreeNode root) {
3 Map<Integer, int[]> best = new TreeMap<>();
4 dive(root, 0, 0, best);
5 List<Integer> view = new ArrayList<>();
6 for (int[] entry : best.values()) view.add(entry[1]);
7 return view;
8 }
9
10 private void dive(TreeNode node, int col, int row, Map<Integer, int[]> best) {
11 if (node == null) return;
12 int[] current = best.get(col);
13 if (current == null || row >= current[0]) best.put(col, new int[]{row, node.val});
14 dive(node.left, col - 1, row + 1, best);
15 dive(node.right, col + 1, row + 1, best);
16 }
17}Optimal — Breadth-First: The Last Node to Reach a Column Wins
OptimalWalk level by level with a queue, carrying each node's column alongside it. Breadth- first order delivers nodes from the top row down and, inside a row, from left to right — so the LAST node to arrive in a column is the lowest, and among equally low nodes the most rightward. Simply overwrite the column's stored value every time a node arrives; whatever remains at the end is the visible node. No row comparisons are needed. O(n) to process the nodes (a tree map or a final sort orders the columns).
O(n)O(n)1class Solution {
2 public List<Integer> bottomEdgeView(TreeNode root) {
3 Map<Integer, Integer> seen = new TreeMap<>();
4 if (root == null) return new ArrayList<>();
5 Queue<TreeNode> nodes = new ArrayDeque<>();
6 Queue<Integer> cols = new ArrayDeque<>();
7 nodes.add(root);
8 cols.add(0);
9 while (!nodes.isEmpty()) {
10 TreeNode node = nodes.poll();
11 int col = cols.poll();
12 seen.put(col, node.val);
13 if (node.left != null) {
14 nodes.add(node.left);
15 cols.add(col - 1);
16 }
17 if (node.right != null) {
18 nodes.add(node.right);
19 cols.add(col + 1);
20 }
21 }
22 return new ArrayList<>(seen.values());
23 }
24}