Binary Tree Right Side View
Medium · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
Stand to the right of a binary tree and look at it. On each level you see only the node that is furthest to the right; the others on that level hide behind it. Given the root, return the values you see, from top to bottom. The empty tree gives [].
The node you see is not always a right child, and not always in the root’s right subtree. When the right side is shorter, a node from the left side shows through on the deeper levels — and walking down the right edge from the root misses exactly those.
Trees here are at most 500 levels deep, so a recursive solution is safe.
The node type and two helpers are provided:
Examples
Input: root = [1,2,3,None,5,None,4] Output: [1,3,4]
The rightmost node on each level is 1, then 3, then 4. Node 5 is on the same level as 4, hidden behind it.
Input: root = [1,2,3,4] Output: [1,3,4]
The right side stops at 3, so on the third level the only node is 4, from the left subtree, and that is the one you see.
Constraints
- 0 <= number of nodes <= 10^4 (LeetCode stops at 100; the bigger tests here let a slow approach show)
- -100 <= Node.val <= 100
- the tree is at most 500 levels deep
Approaches
- Search each depth separately from the root — time O(n · h), space O(h)
Related problems
Start free on Cariara · Coding problems · System design studio
