Problem overview
The function rightSideView receives the root of a binary tree and returns the values of the nodes you would see standing on its right side, from top to bottom. The lesson provides the TreeNode type, a struct with an integer Val and two pointers, Left and Right, which are nil when a child is missing.
From the right you see exactly one node per level: the rightmost one. For the tree with root 1, children 2 and 3, and grandchildren 5 (under 2) and 4 (under 3), the answer is [1 3 4]. On the second level 3 hides 2, and on the third level 4 hides 5.
The rightmost node of a level is not always a right child. In the tree with root 1, children 2 and 3, and a single grandchild 4 under 2, the answer is also [1 3 4]: nothing stands to the right of 4, so it is visible even though it belongs to the left subtree. An empty tree returns an empty slice.
Approach: walk the tree one level at a time
A tempting shortcut is to follow only the right children from the root. It works when the right side reaches the bottom of the tree, and fails otherwise: on the second tree above it gives [1 3] and misses the 4.
The reliable idea is a level order traversal. Keep a queue of nodes waiting to be visited, and process it in rounds. At the start of each round the queue holds exactly one level of the tree. Count the nodes in it, take that many out from the front, and add each node's children to the back, left first and then right. The children belong to the next level, so they wait behind the current one. The last node taken out in a round is the rightmost node of that level, so its value goes into the result.
Every node enters and leaves the queue once, so the work is proportional to the number of nodes. A depth-first search that remembers the depth can also solve the problem, but this lesson uses the queue.
Tracing the first example
Printing each round's nodes in the order they leave the queue for the first tree gives:
level 1 [1]
level 2 [2 3]
level 2 [5 4]The last value of each round, 1, 3 and 4, is the answer.
Step by step
- Create
resultas an empty[]int. It collects one value per level. - Handle the empty tree. If
root == nil, returnresultat once, because the queue needs a first node to start from. - Create the queue as a slice of node pointers holding the root. The first element is the front, and
appendadds at the back. - Loop while the queue is not empty. Go has no
while, sofor len(queue) > 0plays that role. Each pass handles one whole level. - Store
len(queue)inlevelSizebefore touching the queue. At that moment it holds exactly one level. - Loop
ifrom 0 tolevelSize - 1. Children added during this loop belong to the next level, and counting up to the saved size stops the loop before it reaches them. - Take the next node from
queue[0]and drop it withqueue = queue[1:]. - Record the last node of the level. When
i == levelSize-1, appendnode.Valtoresult. - Enqueue the left child if it is not
nil. - Enqueue the right child the same way. Adding left before right keeps each level in left-to-right order.
- Return
resultafter the loops.
The solution in Go
func rightSideView(root *TreeNode) []int {
result := []int{}
if root == nil {
return result
}
queue := []*TreeNode{root}
for len(queue) > 0 {
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
if i == levelSize-1 {
result = append(result, node.Val)
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return result
}The Go details worth a closer look:
- A slice as a queue.
queue[1:]is a slice that starts one element later. It does not copy anything, so removing from the front is cheap.appendadds at the end and may allocate a bigger backing array when there is no room. - Pointers in the slice. The queue has type
[]*TreeNode, so it stores pointers to the nodes, not copies of them. Comparing a child withniltells you whether it exists. - Reassigning after
append.appendreturns the slice that may be longer, so you must store it back:result = append(result, node.Val). Callingappendalone would discard the new element. - The loop bound is fixed.
i < levelSizeuses the number saved before the loop. Writingi < len(queue)would compare against a length that changes as nodes leave and children arrive. []int{}versusnil. The function returns an empty, non-nil slice for an empty tree. Printed, it looks like[], and itslenis 0.
Complexity
Time: O(n) for a tree of n nodes. Each node is added to the queue once and removed once, and each removal does a constant amount of work.
Space: O(n) in the worst case. The queue holds at most about two levels at a time, and a complete tree has roughly n / 2 nodes in its last level. The result holds one value per level, which is never more than n.
Edge cases and common mistakes
- Empty tree.
rightSideView(nil)returns an empty slice, with length 0. Without the early return, the queue would start with anilpointer andnode.Valwould panic. - Single node. A tree with only the value 7 gives
[7]. - Only left children. A chain 1, 2, 3 going left each time gives
[1 2 3], since each node is alone on its level. Following only right children would return just[1]. - Left subtree deeper than the right. With root 1, children 2 and 3, 2 having children 4 and 6, and 4 having a child 8, the answer is
[1 3 6 8]. The 6 and the 8 come from the left subtree. - Repeated values. A root 4 with two children that are both 4 gives
[4 4]. The result lists one value per level, so equal values on different levels still appear separately. - Taking only right children. On the second example tree this gives
[1 3], missing 4. - Forgetting to save the level size. The count must be read before the inner loop starts, or the loop mixes the current level with the next one.
Testing
- Root 1, children 2 and 3, grandchildren 5 (under 2) and 4 (under 3) gives
[1 3 4]. - Root 1, children 2 and 3, grandchild 4 under 2 gives
[1 3 4]. nilgives[].- A single node 7 gives
[7]. - A left-only chain 1, 2, 3 gives
[1 2 3].
