Problem overview
The method rightSideView receives the root of a binary tree, as an optional TreeNode?. Imagine standing on the right of the tree and looking at it: on every level you see exactly one node, the rightmost one. The method returns those values from the top level to the bottom one. An empty tree (root is nil) shows nothing, so the answer is [].
The lesson provides the TreeNode class: each node has a val of type Int and two optional children, left and right. In the example [1,2,3,nil,5,nil,4], node 1 is the root, its children are 2 and 3, node 2 has only a right child (5) and node 3 has only a right child (4). The levels are [1], [2, 3] and [5, 4], and the last value of each level is what you see: [1, 3, 4].
Approach: visit the tree one level at a time
The tempting shortcut is to start at the root and keep going to the right child. It works when every level has a right node, and it fails otherwise. For the tree [1,2,3,4], the third level holds only node 4, which hangs under node 2 on the left. Following right children gives [1, 3], but the correct answer is [1, 3, 4], because nothing stands to the right of 4 and you see it. In the same way, the tree [1,2,nil,3,nil,4], which has no right children at all, must give [1, 2, 3, 4], while the shortcut returns [1].
So the question has to be asked per level: which node is the last one when the level is read from left to right? That is what a level order traversal (breadth-first search) gives. A queue starts with the root. In each round the queue holds exactly one level. The round takes those nodes out from the front, and each node adds its children, left first and then right, at the back. Those children wait for the next round, so the nodes of a level always leave the queue from left to right. The last node taken out in a round is the one you see.
On the example, the rounds see these levels:
level [1]
level [2, 3]
level [5, 4]The last value of each line is the answer: 1, 3 and 4.
Step by step
- Create
result, an empty[Int]. It collects one value per level. - Handle the empty tree.
guard let root = root else { return result }unwraps the optional. Below theguard,rootis a plainTreeNode, and an empty tree has already returned[]. - Create the queue as an array holding
root, plus an indexheadthat starts at 0. The waiting nodes are the ones fromheadto the end of the array. Taking a node out means readingqueue[head]and movingheadforward, which costs O(1). CallingremoveFirst()would shift every remaining element each time. - Loop while
head < queue.count, that is, while some node is still waiting. Each pass of this loop handles one whole level. - Store the level's size,
queue.count - head, in the constantlevelSize. At this moment the waiting nodes are exactly one level, so this is how many nodes to take out in this round. The children appended during the round makequeue.countgrow, which is why the size has to be read once, before the inner loop. - Loop over
0..<levelSizewithi. The loop stops before it reaches the children that were added during this round. - Take the next node: read
queue[head]intonodeand dohead += 1. - Record the last node of the level. When
i == levelSize - 1, appendnode.valtoresult. The node may come from the left subtree, and that is fine, because we look at levels and not at the right children only. - Queue the left child with
if let left = node.left, appendingleftinside the block. - Queue the right child the same way, right after the left one, so that the rightmost node of the next level is the last to enter.
- Return
resultafter the loops.
The solution in Swift
class Solution {
func rightSideView(_ root: TreeNode?) -> [Int] {
var result = [Int]()
guard let root = root else {
return result
}
var queue = [root]
var head = 0
while head < queue.count {
let levelSize = queue.count - head
for i in 0..<levelSize {
let node = queue[head]
head += 1
if i == levelSize - 1 {
result.append(node.val)
}
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
}
return result
}
}
The Swift details worth a closer look:
guard let root = root. The new constant has the same name as the parameter and hides it for the rest of the method. Aguardbody must leave the method, so after it the code can rely onrootbeing non-nil.var queue = [root]. Swift infers[TreeNode].TreeNodeis a class, so the array holds references to the nodes and nothing is copied when they are appended.if let left = node.left.leftandrightare optionals.if letruns its block only when a child exists, so nonilever enters the queue.0..<levelSize. The half-open range stops beforelevelSize. BecauselevelSizeis at least 1 inside the loop, the range is never reversed, which in Swift would be a run-time error.
Complexity
Time: O(n) for a tree of n nodes. Each node enters the queue once and leaves it once, and each visit does a constant amount of work.
Space: O(n) extra. The array keeps every node it has ever held, because head only moves forward and nothing is removed, so it ends with all n nodes. The part that is waiting at any moment is at most about two levels, which is also O(n) in the worst case. Without the head trick, the queue would hold only the waiting nodes, but each removeFirst() would cost O(n).
Edge cases and common mistakes
- Empty tree.
rootisnil, theguardreturns[], and the queue code is never reached. - Single node. The tree
[7]gives[7]: one level, and its only node is also its last. - Only following right children. On
[1,2,3,4]it returns[1, 3]and misses 4. On[1,2,nil,3,nil,4]it returns[1]. - Forgetting
head += 1. The same node is read again and again, and the outer loop never ends. - Repeated values. Values may repeat, and that doesn't matter: the method looks at positions in the tree and never compares values. The tree
[5,5,5,5,5]gives[5, 5, 5], one 5 per level.
Testing
[1,2,3,nil,5,nil,4]gives[1, 3, 4].[1,2,3,4]gives[1, 3, 4].[1,2,nil,3,nil,4]gives[1, 2, 3, 4].[1,nil,2,nil,3]gives[1, 2, 3].[1,2,3,4,5,6,7]gives[1, 3, 7].[]gives[].
