Problem overview
The function rightSideView receives the root of a binary tree and returns the values you would see standing on its right side, from the top level down. The lesson provides the TreeNode class: each node has a val and two children, left and right, which are None when missing.
From the right, exactly one node of each level is visible: the rightmost one. For the tree [1, 2, 3, None, 5, None, 4], the first level is just 1. On the second level 3 hides 2, and on the third level 4 hides 5, so the answer is [1, 3, 4]. An empty tree has no levels, so the answer is [].
The visible node of a level is not always a right child. For [1, 2, 3, 4] the third level holds only 4, which is the left child of 2, and nothing stands to its right. The answer is still [1, 3, 4].
Approach: visit the tree one level at a time
A tempting shortcut is to follow right pointers from the root. On [1, 2, 3, 4] that gives [1, 3] and misses the 4, because the right branch ends one level too early. The answer depends on whole levels, so the solution should walk the tree level by level.
That is a breadth-first search with a queue. The queue starts with the root. At the start of each round it holds exactly one level of the tree. The round counts those nodes, takes them out from the front one at a time, and puts their children at the back. Those children wait for the next round, and since the left child goes in before the right one, each level stays in left-to-right order. The last node taken out in a round is the rightmost node of its level, so its value goes into the answer.
Running the loop on the first example and printing the queue at the start of each round gives:
level [1] -> 1
level [2, 3] -> 3
level [5, 4] -> 4Each line shows the values in the queue and the one that is recorded. The third round shows why the order matters: 5 is the right child of 2 and 4 is the right child of 3, and 4 comes last because 2 was processed before 3.
A depth-first search can solve this too, but the queue keeps the idea close to the question: one round per level, one value per round.
Step by step
- Create
result, an empty list that will receive one value per level. - Handle the empty tree. If
rootisNone, return the emptyresultright away, because the queue below needs a first node. - Create the queue with
deque([root]). Adequeremoves its first element quickly withpopleft(), whilelist.pop(0)has to shift every other element. - Loop while the queue is not empty. Each pass of this
whileloop handles one whole level. - Store
len(queue)inlevelSize. At this moment the queue holds this level and nothing else, so the number is the level's width. - Loop
ioverrange(levelSize). The children added during this loop belong to the next level, and counting up tolevelSizestops the loop before it reaches them. - Take the next node from the front with
queue.popleft(). - Record the last node of the level. When
i == levelSize - 1, appendnode.valtoresult. - Queue the left child if it exists.
- Queue the right child if it exists, right after the left one.
- Return
resultafter the loops.
The solution in Python
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
queue = deque([root])
while queue:
levelSize = len(queue)
for i in range(levelSize):
node = queue.popleft()
if i == levelSize - 1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
The Python details worth a closer look:
- Truthiness.
not rootis true whenrootisNone, andif node.left:is true when the child exists. ATreeNodeobject is truthy by default, even when itsvalis 0, so these tests look at the node, not at its value. - A deque in a
whilecondition. An emptydequecounts as false, sowhile queue:runs until there is nothing left to visit. - The length is read once.
levelSize = len(queue)is taken before the inner loop starts and then stays fixed, while the queue itself keeps growing as children are added.iis the position within the level, which is what identifies its last node.
Complexity
Time: O(n). Every node enters the queue once and leaves it once, and each visit does a constant amount of work.
Space: O(n). The queue holds at most two neighbouring levels at a time, and the widest level of a tree can hold a large share of its nodes, for example about half of them in a perfect tree. The answer itself has one value per level, which is at most n.
Edge cases and common mistakes
- An empty tree.
[]returns[]. Without the early return,deque([None])would sendNoneinto the loop and fail onnode.left. - A single node.
[7]returns[7]: one level, one node, and it is the last of its level. - Following only right children. It gives
[1, 3]for[1, 2, 3, 4], missing the left-subtree node on the third level. - A tree that leans left.
[1, 2, None, 3, None, 4]returns[1, 2, 3, 4]: every level has one node, so every node is visible. - Equal values.
[5, 5, 5, 5, 5]returns[5, 5, 5]. The answer holds one value per level, even when values repeat. - Re-reading the length. Comparing against
len(queue)after children have been added counts nodes of the next level too, so the loop mixes two levels and the "last node" test points at the wrong node. - Pushing the right child first. The level then runs right to left, and the last node of a round becomes the leftmost one.
Testing
[1, 2, 3, None, 5, None, 4]gives[1, 3, 4].[1, 2, 3, 4]gives[1, 3, 4].[]gives[].[7]gives[7].[1, None, 2, None, 3]gives[1, 2, 3].[1, 2, 3, 4, 5, 6, 7]gives[1, 3, 7].
