Problem overview
The method rightSideView receives the root of a binary tree, or null for an empty tree. It returns the values of the nodes you would see standing on the right side of the tree, from the top level to the bottom. The lesson provides the TreeNode class, with the fields val, left and right.
From the right you see one node per level: the rightmost one, which is the last node when the level is read from left to right. For the tree written in level order as [1, 2, 3, null, 5, null, 4], the first level is 1. On the second level 3 hides 2, and on the third level 4 hides 5, so the answer is [1, 3, 4]. For [1, 2, 3, 4] the answer is also [1, 3, 4]: the third level holds only 4, which sits in the left subtree, but nothing is to its right, so it is visible. An empty tree gives [].
Approach: walk the tree one level at a time
A tempting shortcut is to follow only right children from the root. On [1, 2, 3, 4] that visits 1 and then 3, and returns [1, 3], missing the 4. The rightmost node of a level can belong to the left subtree whenever the right subtree is shallower, so the solution has to look at whole levels.
Visiting a tree level by level is the job of a queue: nodes leave from the front, and their children enter at the back. If the queue holds exactly one level at the start of a round, then taking out that many nodes empties the level while the children of those nodes pile up behind, forming the next level. The last node taken out in a round is the rightmost node of its level, and that is the value to record.
Each node enters and leaves the queue once, so the time is O(n) for a tree of n nodes.
A queue without shift()
JavaScript arrays have shift(), which removes the first element, but it moves every other element one place to the left, so it can be slow on long arrays. The lesson uses a cheaper trick: keep the array as it is and a counter head that marks the next node to take. The nodes from head to the end of the array are the ones still waiting. Reading queue[head] and then incrementing head costs O(1). The visited nodes stay in the array, which is fine here because they are only a few references.
Step by step
- Create
resultas an emptynumber[]. It will collect one value per level. - Handle the empty tree. If
!root, returnresultright away. The queue needs a first node to start from, and an empty tree shows nothing. - Create the queue as a
TreeNode[]that holdsroot, and setheadto 0. - Loop while
head < queue.length. As long as some node is waiting, there is another level to handle. Each pass of this loop handles exactly one level. - Store the level's size as
queue.length - headin a constant namedlevelSize. At this point the waiting nodes are one whole level and nothing else. - Loop
ifrom 0 tolevelSize - 1. The constant matters: the loop adds children toqueuewhile it runs, so readingqueue.length - headin the loop condition would keep growing and run into the next level. Counting to a number fixed in advance stops at the end of this level. - Take the next node: read
queue[head]intonodeand advancehead. - Record the last node of the level: when
i === levelSize - 1, pushnode.valontoresult. - Enqueue the left child if it exists. It waits behind the rest of this level.
- Enqueue the right child if it exists, right after the left one, so every level stays in left-to-right order.
- Return
resultafter the loops.
The solution in TypeScript
class Solution {
rightSideView(root: TreeNode | null): number[] {
const result: number[] = [];
if (!root) {
return result;
}
const queue: TreeNode[] = [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 TypeScript details:
TreeNode | null. The parameter can be a node ornull. Theif (!root)check returns early fornull, so the code after it can userootas a node.- Truthiness checks.
if (node.left)is true for any node object and false fornull, so it tests for a missing child before pushing it. - Annotations are erased.
number[]andTreeNode[]help the compiler and disappear in the generated JavaScript, so they cost nothing at run time. constinside loops.levelSizeandnodeare created again on every pass, which is what you want, whileheadis declared withletbecause it changes.
Complexity
Time: O(n). Every node is added to the queue once and read once, and each of those steps takes constant time.
Space: O(n). The array keeps every node that has been visited, since nothing is removed. Even if you removed them, the queue holds up to a whole level at a time, and in a complete tree the last level has about half of the nodes. The result array is small by comparison: one value per level.
Edge cases and common mistakes
- Empty tree. Without the early return,
[root]would holdnull, and readingnode.valwould throw. With it,[]gives[]. - Single node. A tree with only the root 7 gives
[7]. - Following only right children. It gives
[1, 3]for[1, 2, 3, 4]instead of[1, 3, 4], as explained above. - Only a left spine. The tree
[1, 2, null, 3, null, 4]has no right children at all, yet the answer is[1, 2, 3, 4], because each level's only node is visible. - Enqueueing the right child first. The last node of a level would then be the leftmost one, and you would return the left side view instead.
- Recording the first node of a level. The same left-side mistake. The check must be on the last index,
levelSize - 1. - Values may repeat. The result holds values, not nodes, and the algorithm never compares values, so duplicates change nothing.
Testing
These inputs are level-order lists, with null for a missing child, and the outputs are what the solution returns.
[1, 2, 3, null, 5, null, 4]gives[1, 3, 4].[1, 2, 3, 4]gives[1, 3, 4].[]gives[].[7]gives[7].[1, 2, null, 3, null, 4]gives[1, 2, 3, 4].[1, null, 2, null, 3]gives[1, 2, 3].
