LeetCode 199 · Medium · Trees

Binary Tree Right Side View

Stand to the right of a binary tree and look at it: on each level you see only the rightmost node. Return those values from top to bottom.

O(n)time
O(w)space · widest level
BFSlast node of each level

level order as on LeetCode, null = no child · up to 15 nodes, 4 levels · values −99 to 99

Queue LinkedList · poll() at the front (left), add() at the back · null entries ride along · yellow = this level

res one value per level, the last node seen on it

public List<Integer> rightSideView(TreeNode root) { List<Integer> res = new ArrayList<>(); Queue<TreeNode> q = new LinkedList<>(); // allows null entries q.add(root); while (!q.isEmpty()) { TreeNode rightSide = null; int qLen = q.size(); for (int i = 0; i < qLen; i++) { TreeNode node = q.poll(); if (node != null) { rightSide = node; q.add(node.left); q.add(node.right); } } if (rightSide != null) { res.add(rightSide.val); } } return res;}
level
—
qLen
—
node
—
rightSide
—
res
[]

Why it works

  1. Brute force collects every level in full (Level Order Traversal, 102) and keeps the last value of each list. Same O(n) time, but it stores every level's values.
  2. Within a level, the queue holds nodes left to right. So the last real node popped in a level is the one you see from the right. rightSide is overwritten by every real node and ends on that one.
  3. Each node is added and polled once: O(n) time. The queue holds at most one level plus its children, O(w) for the widest level. It is a LinkedList because ArrayDeque throws NullPointerException on add(null).
  4. Pitfall: following right children only. In "left side peeks out", the bottom level has no right-hand node at all, yet 6 is visible because it is the rightmost node on that level.
  5. DFS alternative: visit right before left and record a node when its depth equals res.size(): the first node reached at each depth is the rightmost.