Problem overview
rightSideView(root) receives the root of a binary tree and returns the values you would see standing on its right side, from the top level down. From the right you see one node per level: the rightmost one. An empty tree (root is null) shows nothing, so the result is [].
The lesson provides the node class: a TreeNode with val, left and right, where a missing child is null. For [1,2,3,null,5,null,4] the levels are [1], [2, 3] and [5, 4]. The rightmost nodes are 1, 3 and 4, so the answer is [1, 3, 4].
Approach: visit the tree one level at a time
A tempting shortcut is to follow root.right again and again. It works for the first example, but it fails as soon as the right subtree is shallower than the left one. For [1,2,3,4] the node 4 is the only node on its level. It hangs under 2, yet nothing hides it, so it must appear. Following right children alone returns [1, 3], while the correct answer is [1, 3, 4].
The reliable idea is to process the tree level by level, which is a breadth-first search with a queue. Nodes leave the queue in the order they entered, and each node's children (left first, then right) join the back. If you count how many nodes are waiting at the start of a round, you know exactly where the level ends: the last node taken out in that round is the rightmost one of its level.
Every node enters and leaves the queue once, so the work is proportional to the number of nodes.
Step by step
- Create
result, an empty array that will receive one value per level. - Handle the empty tree. If
!root, returnresultstraight away. The queue needs a first node to start from. - Create the queue as an array holding
root, plus an indexheadthat starts at 0. The waiting nodes are those fromheadto the end of the array. Reading atheadand moving it forward is cheaper than callingshift(), which has to move every remaining element. - Loop while nodes are waiting:
head < queue.length. Each pass of this loop handles one whole level. - Store the level's size in
levelSize, computed asqueue.length - headbefore any node of the level is taken out. It must be fixed up front, because the queue grows while the level is processed. - Loop
ifrom 0 tolevelSize - 1. The children that get added during this loop belong to the next level, and counting tolevelSizekeeps the loop from reaching them. - Take the next node: read
queue[head]intonodeand dohead++. - Record the last node of the level. When
i === levelSize - 1, pushnode.valontoresult. That node can come from the left subtree, which is why the code looks at positions in the level and not at right children. - Queue the left child if it exists.
- Queue the right child if it exists. Left goes in first, so each level stays in left-to-right order.
- Return
resultafter the loops.
The solution in JavaScript
class Solution {
rightSideView(root) {
const result = [];
if (!root) {
return result;
}
const queue = [root];
let head = 0;
while (head < queue.length) {
const levelSize = queue.length - head;
for (let i = 0; i < levelSize; i++) {
const node = queue[head];
head++;
if (i === levelSize - 1) {
result.push(node.val);
}
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
}
return result;
}
}
A few JavaScript details:
- The queue is a plain array.
pushadds at the end. Nothing is ever removed:headmarks how far the front has moved, so the nodes before it are simply finished. if (!root)andif (node.left)rely on truthiness. An object is truthy andnullis falsy, so the checks mean "exists". This is safe here because a node is always an object, never a falsy number.levelSizeis aconstinside thewhilebody. A new constant is created in each round, which is what you want, because the size changes from level to level.- The result holds numbers, copied from
node.val, so later changes to the tree can't affect it.
Trace on [1,2,3,4]
Printing each round of the while loop for this tree shows the levels and their last nodes:
level 1 levelSize 1 last 1
level 2,3 levelSize 2 last 3
level 4 levelSize 1 last 4
The third level contains only node 4, so it is the last node of its level and it is recorded, even though it sits in the left subtree.
Complexity
Time: O(n). Each of the n nodes is put in the queue once and taken out once, with a constant amount of work each time.
Space: O(n). The array queue is never shortened, so by the end it has held all n nodes. Even if it were trimmed, a level of a wide tree can hold about half of the nodes, so the extra space would still be O(n) in the worst case. The answer itself has one value per level.
Edge cases and common mistakes
- Empty tree.
[]gives[]. Without the early return,queuewould start withnullandnode.leftwould throw aTypeError. - Following only right children. It returns
[1, 3]for[1,2,3,4]instead of[1, 3, 4], and just[1]for[1,2,null,3,null,4], where the right answer is[1, 2, 3, 4]. - Recording the first node of each level gives the view from the left. On
[1,2,3,null,5,null,4]that returns[1, 2, 5]instead of[1, 3, 4]. - Reading the level size after the level started. The size must be stored before the inner loop. Computing it again while children are being added mixes two levels together.
- Skipping the left child. The last node of a level may be a left child, so both children must be queued.
- A single node.
[7]gives[7].
Testing
[1,2,3,null,5,null,4]gives[1, 3, 4].[1,2,3,4]gives[1, 3, 4].[1,2,null,3,null,4]gives[1, 2, 3, 4].[1,null,2,null,3]gives[1, 2, 3].[1,2,3,4,5,6,7]gives[1, 3, 7].[7]gives[7].[]gives[].
