What You See Looking Down 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 down at the tree from above, in each column you see only the node nearest to the top; if two nodes are equally high in a column, you see the one that comes first in level order. Return the visible values from the leftmost column to the rightmost.
A breadth-first walk hands you nodes in top-to-bottom order, so the first node to reach a column is the one you would see.
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 down from above, in each column you see only the node closest to the top (smallest row). If two nodes tie for that (same row, same column), the one that comes first in level order (the more leftward) 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 Shallowest 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 shallowest node seen so far, and replace it only when a strictly shallower node is found (so on a tie the earlier one — the more leftward one — stays). Because a depth-first walk reaches nodes in an arbitrary vertical order, it has to compare rows explicitly for every node. At the end, read the columns from left to right (keeping them sorted costs O(log n) per column in a tree map, or one sort at the end).
O(n log n)O(n)1class Solution {
2 public List<Integer> topEdgeView(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 First Node Reaching a Column Is the Visible One
OptimalWalk level by level with a queue, carrying each node's column alongside it. A breadth-first walk reaches nodes in order of increasing row, and within a row from left to right — so the FIRST node that arrives in a column is automatically the topmost, and the earliest among equally-high ones. Record a column's value only when the column has not been seen before, and ignore everything later. There are no row comparisons at all. Every node is queued once (O(n)); the final left-to-right reading of at most 2n + 1 columns is a single pass, as they lie in a contiguous range (the tree map or the sorted column list adds a log factor in general).
O(n)O(n)1class Solution {
2 public List<Integer> topEdgeView(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.putIfAbsent(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}