Problem overview
The method rightSideView receives the root of a binary tree, which may be null for an empty tree. It returns a List<Int> with the one node you would see on each level if you stood to the right of the tree, from the top level down. That node is the rightmost one on its level.
The lesson provides the TreeNode class: it has a value and two nullable children, left and right, both declared with var. For the tree [1,2,3,null,5,null,4], level 1 is 1, level 2 is 2, 3 and level 3 is 5, 4. The rightmost nodes are 1, 3 and 4, so the answer is [1, 3, 4].
Approach: visit the tree one level at a time
A tempting shortcut is to start at the root and keep following right children. It works when every level has a right-hand node, and it fails as soon as a level is reached only through the left subtree. For the tree [1,2,3,4], level 3 holds only the node 4, which hangs under 2. Following right children gives [1, 3] and misses it, while the correct answer is [1, 3, 4]. Walking right children only on [1,2,null,3] returns [1] where the answer is [1, 2, 3].
The reliable approach is a breadth-first search. A queue visits the nodes level by level, and the last node taken out for each level goes into the answer. The fact that makes this work: at the start of every round of the outer loop, the queue holds exactly one level, nothing more and nothing less. Taking out all those nodes while adding their children to the back leaves exactly the next level in the queue.
Every node enters the queue once and leaves it once, so the work is proportional to the number of nodes.
Step by step
- Create
resultwithmutableListOf<Int>(). It receives one value per level. - Return
resultfor an empty tree. The queue needs a first node, and an empty tree shows nothing. - Create the queue and add the root. After the
nullcheck, Kotlin knowsrootis aTreeNode, so it can go in a queue of non-null nodes. - Loop while the queue is not empty. One pass of this loop handles one whole level.
- Record
levelSize, the currentqueue.size. This is the number of nodes on the level being handled. The size must be read before the inner loop starts, because that loop keeps adding children, and the queue grows. - Loop
iover0 until levelSize. It stops after the last node of the level, before it reaches the children that were just added. - Take the next node with
removeFirst(). The nodes of a level come out from left to right. - Save the last one. When
i == levelSize - 1, this is the level's rightmost node, so its value goes intoresult. - Queue the left child when it exists.
- Queue the right child when it exists. Left goes in before right, so the rightmost node of the next level is always the last of that level in the queue.
- Return
resultafter the loops.
The solution in Kotlin
class Solution {
fun rightSideView(root: TreeNode?): List<Int> {
val result = mutableListOf<Int>()
if (root == null) {
return result
}
val queue = ArrayDeque<TreeNode>()
queue.add(root)
while (queue.isNotEmpty()) {
val levelSize = queue.size
for (i in 0 until levelSize) {
val node = queue.removeFirst()
if (i == levelSize - 1) {
result.add(node.value)
}
if (node.left != null) {
queue.add(node.left!!)
}
if (node.right != null) {
queue.add(node.right!!)
}
}
}
return result
}
}
Kotlin details worth knowing:
ArrayDequeis Kotlin's own. Without an import,ArrayDequeiskotlin.collections.ArrayDeque.addputs an element at the back andremoveFirst()takes one from the front, both in constant time. It is a better choice than removing from the front of aMutableList, which has to shift every other element.- Why
node.left!!? The checknode.left != nulldoesn't let Kotlin treatnode.leftas non-null afterwards, becauseleftis avarthat could change in between. Leaving out the!!gives the compile errorsmart cast to 'TreeNode' is impossible, because 'left' is a mutable property that could be mutated concurrently. The!!says "I just checked, it is not null".rootis a function parameter, which can't change, so it needs no!!. 0 until levelSizeexcludeslevelSize, soiruns from 0 tolevelSize - 1, the position of the last node.- The return type is read-only. The method promises a
List<Int>and hands back aMutableList<Int>. That is fine: the caller just can't add to it through that type.
Tracing the example
Running the solution's loops on [1,2,3,null,5,null,4], and printing the queue at the start of each round, gives:
round 1: queue holds [1], levelSize = 1
i=0: take 1 -> seen
round 2: queue holds [2, 3], levelSize = 2
i=0: take 2
i=1: take 3 -> seen
round 3: queue holds [5, 4], levelSize = 2
i=0: take 5
i=1: take 4 -> seen
Each round starts with exactly one level in the queue, and the node marked "seen" is the last one taken. Node 2 has no left child and node 3 has no left child either, so the next level is 5 (child of 2) and then 4 (child of 3).
Complexity
Time: O(n) for a tree of n nodes. Each node is added to the queue once, removed once, and its two children are checked once.
Space: O(n). The queue holds at most two levels at once, and the widest level of a tree can contain about half of all nodes. The result list is as long as the tree is deep.
Edge cases and common mistakes
- Empty tree. The early return gives
[], and it is also what lets Kotlin treatrootas non-null when it goes into the queue. - A single node.
[7]gives[7]. - Visible nodes in the left subtree.
[1,2,3,4]gives[1, 3, 4], and[1,2,null,3]gives[1, 2, 3]: when the right side runs out, the left side shows through. Only level-by-level processing gets this right. - Repeated values. The tree
[5,5,5,5,5]gives[5, 5, 5]: one value per level, even if all values are equal. The answer depends on positions, never on values. - Mixing levels. If the queue size were not frozen in
levelSizeand the loop ran until the queue was empty, children would blend into the level being handled, and there would be no way to tell which node is the last of its level.
Testing
[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]gives[1, 2, 3].[1,null,2,null,3]gives[1, 2, 3].[5,5,5,5,5]gives[5, 5, 5].
