Right / Left View of Binary Tree
WHAT IT SAYS
Report the nodes visible from the right side of the tree (or the left): exactly one node per level — the outermost one on that side.
WHAT IT'S REALLY ASKING
"The view is one node per depth: whichever the eye hits first. So pick a traversal that reaches the correct side of each level FIRST, and the rule collapses to a single test — is this the first node I have ever seen at this depth? Depth versus answer-length. That's the whole algorithm."
Collect full levels, keep one node from each
O(n) time, O(n) space for the stored levelsRun a standard BFS level-order traversal, store every complete level as a list, then take the last element of each list for the right view (or the first, for the left).
WHERE THE WORK IS WASTED — Honest accounting: this is asymptotically fine and completely correct — the waste is proportional, not asymptotic. You materialise every level in full to keep one element of each; a wide tree stores thousands of nodes per level to sample a single one, and the intermediate lists exist only to be indexed once and discarded. The reason to look further is not that BFS is wrong — it is that the recursive version reveals what a 'view' actually is, and that insight is the reusable part.
The first node seen at each depth IS the view.
Restate what the right view is: for each depth d, the node the eye meets first when looking from the right — the rightmost node of level d. 'Rightmost' is a fact about order WITHIN a depth, so choose a traversal order in which the rightmost node of every level is guaranteed to be visited before its level-mates. DFS visiting root, then RIGHT child, then left child has exactly that property, and here is the argument: at any node, everything in its right subtree is visited before anything in its left subtree — and this holds recursively at every branching. So among all nodes at a given depth, the one reached by taking right-turns as early as possible — the rightmost — is visited first. The traversal order encodes the geometry. Now the detection trick, which is the part worth memorising because it is so clean it looks like a typo: carry the answer list and the current depth. If depth equals the list's current length, this node is the FIRST ever visited at this depth — because depths are discovered in order, the list has exactly one entry per depth already seen — so append it. Otherwise some node at this depth already claimed the view; do nothing. No per-level buffers, no 'last seen' overwriting, no second pass. The answer's own length is the bookkeeping. The left view is the same function with the two recursive calls swapped: visit left before right, and 'first at this depth' becomes the leftmost. One character of difference, which tells you the pattern is about ARRIVAL ORDER, not about sides. The BFS equivalent — keep overwriting each level's slot so the LAST node of the level survives — works too, and generalises differently: it is the right view as 'last arrival', the DFS is 'first arrival with a biased order'. Same set, two framings.
Root-right-left DFS with the depth-equals-length test
O(n) time, O(h) stack space — versus O(w) queue space for the BFS versionRecurse with (node, depth). At each node: if depth equals answer.length, append node's value. Recurse right first, then left. For the left view, recurse left first. The answer builds itself top level to bottom, one node per depth, no post-processing.
Bias the Order, Keep First Arrivals
YOU'LL SEE IT AGAIN WHEN
- The output wants exactly one representative per group (per depth, per column, per component), selected by a positional rule like leftmost or rightmost.
- A traversal order exists in which the desired representative of every group is provably visited before its group-mates.
- Groups are discovered in sequence, so 'is this a new group?' reduces to comparing the group index against the answer's current length.