What You See Looking at the Tree From the Left
Solve this ProblemYou are given the root of a binary tree. Picture yourself standing on its left-hand side, looking towards the tree. At every level you see only the leftmost node of that level; nodes to its right are hidden behind it. Return the values of the visible nodes ordered from the top level to the bottom level.
Building each level completely and taking its first value works. A depth-first walk that always goes left first can find the same values while carrying only the depth.
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 - ◆
Imagine standing to the left of the tree. At each level you see only the leftmost node of that level. Return those visible values from the top level to the bottom. 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 — Level by Level, Build Each Row, Keep Its First Value
GoodWalk the tree level by level with a queue. For each level, build the full row of values from left to right, then take its first value as the visible node. It is easy to trust — the row is exactly the level — but it fills and discards a whole row per level even though only one value of each is used. O(n) time and O(w) space for the queue and the current row.
O(n)O(w)1class Solution {
2 public List<Integer> leftEdgeView(TreeNode root) {
3 List<Integer> view = new ArrayList<>();
4 if (root == null) return view;
5 Queue<TreeNode> queue = new ArrayDeque<>();
6 queue.add(root);
7 while (!queue.isEmpty()) {
8 int size = queue.size();
9 List<Integer> row = new ArrayList<>();
10 for (int i = 0; i < size; i++) {
11 TreeNode node = queue.poll();
12 row.add(node.val);
13 if (node.left != null) queue.add(node.left);
14 if (node.right != null) queue.add(node.right);
15 }
16 view.add(row.get(0));
17 }
18 return view;
19 }
20}Optimal — Depth-First, Left Child First, Record the First Node at Each Depth
OptimalExplore depth-first, always going to the LEFT child before the RIGHT one, and pass the current depth along. The first node ever reached at a new depth must be the leftmost node of that depth, because everything to its left would have been reached earlier. So keep the answer list: when the depth equals the list's current size, no node of that depth has been seen yet — add this one. Every other visit at an already-recorded depth is ignored. There is no queue and no row: O(n) time and O(h) recursion space.
O(n)O(h)1class Solution {
2 public List<Integer> leftEdgeView(TreeNode root) {
3 List<Integer> view = new ArrayList<>();
4 walk(root, 0, view);
5 return view;
6 }
7
8 private void walk(TreeNode node, int depth, List<Integer> view) {
9 if (node == null) return;
10 if (depth == view.size()) view.add(node.val);
11 walk(node.left, depth + 1, view);
12 walk(node.right, depth + 1, view);
13 }
14}