Problem overview
The method rightSideView receives the root of a binary tree and returns a List<Integer> with the values you would see standing on the tree's right side, from the top level down. From the right you see exactly one node per level: the rightmost one. That node is not always a right child. When the right subtree is shallower than the left one, the node you see on a deep level belongs to the left subtree.
Take the tree [1,2,3,null,5,null,4]. Level 0 is just 1. On level 1, node 3 hides node 2. On level 2, node 4 hides node 5. The answer is [1, 3, 4]. For [1,2,3,4] the third level holds only node 4, which hangs under 2, and nothing stands to its right, so it is visible: the answer is again [1, 3, 4]. An empty tree gives an empty list.
The lesson provides the TreeNode class (it appears in a comment in the starter code), with the fields val, left and right and a constructor that takes the value.
Approach: walk the tree one level at a time
A tempting shortcut is to follow right pointers from the root and collect what you meet. It fails as soon as a right branch ends before a left one does. Run on [1,2,3,4], that shortcut returns [1, 3] instead of [1, 3, 4], and on [1,2,null,3,null,4] (a chain that only goes left) it returns [1] instead of [1, 2, 3, 4].
The reliable idea is to treat the question as "what is the last node of each level?" and visit the tree level by level with a breadth-first search (BFS). A queue makes this natural: nodes leave from the front in the order they arrived, and each node's children join at the back. If the queue holds exactly one level at the start of a round, then after that round the children of that level, and nothing else, are waiting for the next round.
Inside a round, the nodes come out from left to right, because the left child is always added before the right one. So the last node taken out in a round is the rightmost node of its level, and that is the one to record.
Step by step
- Create
result, anArrayListthat will receive one value per level. - Return it right away for an empty tree. The queue needs a first node to start from, and an empty tree shows nothing.
- Create the queue as an
ArrayDeque, declared as aDeque<TreeNode>, and add the root.addputs a node at the back;polltakes one from the front. - Loop while the queue is not empty. One pass of this loop handles one whole level.
- Store
queue.size()inlevelSize. At this moment the queue holds exactly one level. The number must be saved first, because the size changes as children are added during the round. Readingqueue.size()in the loop condition instead would mix the next level into the current one. - Visit the level with a
forloop that countsifrom 0 up tolevelSize. - Take the next node with
queue.poll(). - Record the last one. When
i == levelSize - 1, the node is the last of its level, so addnode.valtoresult. - Queue the left child if it exists. It waits behind the rest of the current level.
- Queue the right child if it exists, right after the left one, which keeps every level in left-to-right order.
- Return
resultafter the loops.
The solution in Java
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (i == levelSize - 1) {
result.add(node.val);
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return result;
}
}A few Java details are worth knowing. Deque<TreeNode> is the interface type, and ArrayDeque is the class behind it; both ends are fast. poll() returns null when the queue is empty, but it is only called while the loop knows that levelSize nodes are waiting, so node is never null there. The list holds Integer objects, and result.add(node.val) boxes the int for you.
The children are checked against null before they are added. Without those checks a missing child would enter the queue as null, and the next node.left would throw a NullPointerException.
Complexity
Every node enters the queue once and leaves it once, with constant work in between, so the time is O(n) for a tree of n nodes. The queue holds at most about two levels at once. For a wide tree, such as a complete tree whose last level has about half the nodes, that is O(n) extra space. The result list is the output and is not counted.
Edge cases and common mistakes
- Only following right children. It misses nodes that are visible because the right side is shorter, as the runs above show.
- Using the first node of each level. That gives the left side view instead.
- Not saving the level size. The queue grows while you work, so a loop bounded by the live
queue.size()does not stop at the end of the level. - Forgetting the empty tree.
queue.add(null)on anArrayDequethrows, so the early return matters. - Repeated values. The tree may hold equal values; the method records nodes by position, so duplicates cause no trouble.
Testing
These inputs were run against the solution above, with the trees written in level order:
| Tree | Result |
|---|---|
[1,2,3,null,5,null,4] | [1, 3, 4] |
[1,2,3,4] | [1, 3, 4] |
[] | [] |
[1,null,2,null,3] | [1, 2, 3] |
[1,2,null,3,null,4] | [1, 2, 3, 4] |
[7] | [7] |
