Problem overview
The method RightSideView receives the root of a binary tree and returns a List<int>: the values you would see standing on the right side of the tree, from the top level down. From the right you see exactly one node per level, the rightmost one. An empty tree (root == null) shows nothing, so the result is an empty list.
The lesson provides the TreeNode class, with the fields val, left and right and a constructor TreeNode(int x). For the tree [1,2,3,null,5,null,4], level order with null for a missing child, the levels are 1, then 2 3, then 5 4. The rightmost nodes are 1, 3 and 4, and the method returns [1,3,4]. For [1,2,3,4] the last level holds only 4, which sits under the left child. Nothing hides it, so it is visible and the answer is [1,3,4] again.
Approach: walk the tree one level at a time
The tempting shortcut is to follow right pointers from the root. It works only when every level has a right-hand node. On [1,2,3,4] it returns [1,3] and misses the 4, and on [1,2,null,3] it returns just [1], while the correct answer is [1,2,3]. The visible node is the last node of a level, whichever subtree it belongs to.
So the method needs to look at the tree level by level. A Queue<TreeNode> does this. It is first in, first out: Enqueue adds at the back, Dequeue removes from the front, and Count says how many nodes wait inside. The idea is a loop in which each pass handles one whole level:
- At the start of a pass, the queue holds exactly the nodes of one level, left to right, and nothing else.
- Take the size of the queue first. That is the number of nodes in this level.
- Remove that many nodes. The last one removed is the rightmost of the level, so its value goes into the result.
- While removing a node, put its children at the back, left child first. They form the next level, and they wait behind the rest of this one.
Because the size is read before the inner loop starts, the children added during the pass do not extend it. They are handled in the next pass of the while loop.
Step by step
- Create the result list. A
List<int>namedresultcollects one value per level. - Handle the empty tree. If
root == null, return the empty list. The queue below needs a first node to start from, and puttingnullinto it would crash later onnode.left. - Create the queue and enqueue
root. - Loop while
queue.Count > 0. Each pass of this loop is one level. - Store
levelSize = queue.Count. This fixes how many nodes belong to the level. - Loop
ifrom 0 tolevelSize - 1. This visits exactly the nodes of the level. - Dequeue a node. The nodes leave in left-to-right order.
- Record the last one. When
i == levelSize - 1, the node is the last of its level, so addnode.valtoresult. - Enqueue the left child, then the right child, each only if it is not
null. Left first keeps every level in left-to-right order. - Return
resultafter the loops.
The solution in C#
class Solution {
public List<int> RightSideView(TreeNode root) {
List<int> result = new List<int>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0) {
int levelSize = queue.Count;
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.Dequeue();
if (i == levelSize - 1) {
result.Add(node.val);
}
if (node.left != null) {
queue.Enqueue(node.left);
}
if (node.right != null) {
queue.Enqueue(node.right);
}
}
}
return result;
}
}
The C# details worth knowing:
Queue<T>lives inSystem.Collections.Generic, likeList<T>.Dequeue()on an empty queue throws anInvalidOperationException. The outer loop condition guarantees it never happens here.- Reading
queue.Countonce. Inside theforloop the count keeps changing as nodes leave and children arrive. Writingi < queue.Countin the loop header would mix levels together and make the "last node" test meaningless. Store the size in a variable before the loop. - Reference types and
null.TreeNodeis a class, soleftandrightare references that arenullwhen the child is missing. That is why every child is tested before it is enqueued. - The list is built in level order, so the first level's value comes first. No reversing is needed.
Complexity
Time: O(n) for a tree of n nodes. Each node is enqueued once and dequeued once, and each takes constant work.
Space: O(n). The queue holds at most two neighbouring levels at a time, and a level can hold about half of the nodes in a full tree. The result list adds one value per level, which is at most n.
Edge cases and common mistakes
- Empty tree. Returns an empty list.
- Single node.
[7]gives[7]. - Left-leaning tree.
[1,2,null,3]gives[1,2,3]: every node is the only one on its level, and every one is visible. - Following only right children. It returns
[1,3]for[1,2,3,4]and misses the 4. - Using the queue size inside the loop header. The levels blur together: on
[1,2,3,null,5,null,4]the method returns[3]. - Enqueueing the right child first. The last node of a level would then be the leftmost one, so the method would report the left view instead of the right view.
- Forgetting the
nullchecks. A leaf has twonullchildren, and enqueueing them makes the nextDequeuehand backnull, sonode.leftthrows aNullReferenceException.
Testing
[1,2,3,null,5,null,4]gives[1,3,4].[1,2,3,4]gives[1,3,4].[]gives[].[1,null,3]gives[1,3].[1,2,null,3]gives[1,2,3].[7]gives[7].[1,2,3,4,5,6,7]gives[1,3,7].
