Binary Tree Right Side View
Maintained by Vikas D, software engineer
You are handed a binary tree, but instead of node objects you get a flat array laid out in level-order. Index 0 is the root, and for any node at index i its left child sits at index 2i+1 and its right child at index 2i+2. A null entry means there is no node in that slot.
Picture yourself standing to the right of the tree and looking across it. On each horizontal level you can only see one node: the last one that is actually present on that level. Your job is to collect those visible values from the top level down to the bottom.
The rightmost visible node on a level is not always a right child. If the right subtree is missing at some depth but the left subtree keeps going, the deepest left-side node becomes the one you see. So you cannot just walk right children; you have to look at the whole level and take the last real node on it.
Return the visible values as an array ordered from the top level to the deepest level. An empty input array means there is no tree, so the answer is an empty array.
Examples
Level 0 has only node 1. Level 1 has nodes 2 and 3, so 3 is rightmost. Level 2 has node 5 (right child of 2) and node 4 (right child of 3); 4 is the last real node, so it is visible.
The root 1 has no left child and right child 3. Each level holds a single node, so both are visible.
This is a left-leaning chain. Every level contains exactly one node (1, then 2, then 3, then 4), so each one is the rightmost on its level even though they are all left children.
Constraints
- Node count is in the range 0 to 100.
- Each node value is an integer in the range -100 to 100.
- Input is a level-order array where null represents a missing node.
- An empty array represents an empty tree and returns an empty array.
Visible test cases
- rightSideView([1,2,3,null,5,null,4]) == [1,3,4]
- rightSideView([1,null,3]) == [1,3]
- rightSideView([1]) == [1]
- rightSideView([]) == []
- rightSideView([1,2,3,4,null,null,null]) == [1,3,4]
- rightSideView([1,2,null,3,null,null,null,4]) == [1,2,3,4]
Hints
Hint 1
The answer has one value per level of the tree, so think about processing the tree one level at a time rather than node by node.
Hint 2
From an index i in a level-order array, the children live at 2i+1 and 2i+2. Use that to expand a level into the next level's indices, skipping nulls.
Hint 3
Within a single level, keep scanning left to right and remember the last present node you saw. That last node is the one visible from the right.
Approaches
Level-by-level BFS over indices
Time O(n) where n is the array length, since each index is visited once. · Space O(n) for the frontier indices held across a level plus the output.Walk the tree one level at a time. For each level, scan its nodes left to right and record the last non-null value, which is exactly what the right-side viewer sees.
- Return an empty array immediately if the input is empty.
- Start a frontier holding just index 0 (the root).
- For the current frontier, scan its indices in order, skipping any that are out of range or null, and track the value of the last real node seen.
- While scanning, build the next frontier by pushing the in-range child indices 2i+1 and 2i+2 for each present node.
- If the level had at least one real node, append that last value to the result.
- Replace the frontier with the next level and repeat until the frontier is empty.
Depth-first, right child first
Time O(n), every reachable index is touched once. · Space O(h) recursion stack where h is the tree height, up to O(n) for a degenerate chain.Recurse depth first but always descend the right side before the left. The first time you reach a new depth, that node is the rightmost visible one for its level.
- Track the maximum depth reached so far, starting at zero (no levels recorded).
- Define a recursion that takes an index and a depth, and returns early when the index is out of range or holds null.
- If the current depth equals the number of values collected so far, this node is the first seen at this depth, so append its value.
- Recurse into the right child index 2i+2 first, then the left child index 2i+1, both at depth+1.
- Start the recursion at index 0 and depth 0; the result fills in top-down.
Common mistakes
- Assuming the visible node is always a right child. When the right subtree ends early but the left keeps going, the deepest left node is what shows on that level.
- Computing child positions as 2i and 2i+1 (a 1-indexed formula) instead of 2i+1 and 2i+2 for a 0-indexed array.
- Reading past the array end. Child index 2i+2 can exceed the array length, so bound-check before indexing.
- Treating null entries as real nodes. A null must not produce a visible value and its phantom children must be skipped.
- Mishandling the empty array. With no input there are no levels, so the answer is an empty array, not a crash.
Follow-up variations
- What changes if the input is a real linked node structure with left and right pointers instead of a packed array?
- Could you return the left side view instead, the first present node on each level?
- How would you return every level's full list of values (a standard level-order traversal) and derive the right view from it?
- If the tree could be enormous, how would an iterative depth-first version avoid deep recursion limits?