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 tree's right side, from the top level to the bottom one. Exactly one node of each level is visible, the rightmost one. An empty tree (root == null) gives an empty list.
The lesson provides the TreeNode class (it is shown in a comment above the starter code): class TreeNode(var value: Int), with var left: TreeNode = null and var right: TreeNode = null. A missing child is null.
For the tree [1,2,3,null,5,null,4], level 1 is just 1; level 2 is 2, 3, and 3 hides 2; level 3 is 5, 4, and 4 hides 5. The method returns List(1, 3, 4).
Approach: walk the tree one level at a time
A tempting shortcut is to follow right pointers from the root. It works for the first example, but it fails as soon as a level is reached only through the left subtree. For the tree [1,2,3,4], node 4 is the left child of 2, and nothing stands to its right, so it is visible. Following right pointers gives List(1, 3), while the correct answer is List(1, 3, 4).
The reliable idea is to visit the tree level by level, which is a breadth-first traversal. A queue does it: nodes leave from the front, and their children join at the back. If the queue holds exactly one level at the start of a round, then the last node taken out in that round is the rightmost node of the level, which is the one to record. The children added during the round wait behind the rest of the level, so they form the next round.
A depth-first search can also do the job by tracking the depth, but the queue version matches the way the question is phrased (one value per level) and needs no recursion.
Step by step
- Create
result, an emptyArrayBuffer[Int](). It collects one value per level. - Handle the empty tree. If
root == null, returnresult.toListimmediately. The queue needs a first node to start from. - Create the queue as a
mutable.Queue[TreeNode]holdingroot.enqueueadds at the back,dequeue()removes from the front. - Loop while
queue.nonEmpty. Each pass of this loop handles one whole level. - Record the level's size,
queue.size, inlevelSize. Right now the queue contains only this level, so the number is the count of its nodes. It must be stored before the inner loop, because the queue keeps changing while nodes are added. - Loop
iover0 until levelSize. This takes exactly the nodes of the current level and stops before the children added during the loop. - Dequeue a node. Nodes leave in left-to-right order.
- If
i == levelSize - 1, the node is the last of its level: addnode.valuetoresultwith+=. - Enqueue the left child when it is not
null. - Enqueue the right child when it is not
null, right after the left one, so every level stays in left-to-right order. - Finish with
result.toList, the last expression of the method.
The solution in Scala
class Solution {
def rightSideView(root: TreeNode): List[Int] = {
val result = ArrayBuffer[Int]()
if (root == null) {
return result.toList
}
val queue = mutable.Queue[TreeNode](root)
while (queue.nonEmpty) {
val levelSize = queue.size
for (i <- 0 until levelSize) {
val node = queue.dequeue()
if (i == levelSize - 1) {
result += node.value
}
if (node.left != null) {
queue.enqueue(node.left)
}
if (node.right != null) {
queue.enqueue(node.right)
}
}
}
result.toList
}
}
Scala details worth a look:
0 until levelSizeexcludeslevelSize, soiruns from0tolevelSize - 1, one turn per node of the level.0 to levelSizewould includelevelSizeand take one turn too many.queue.sizeis read once. The inner loop enqueues children, so readingqueue.sizeagain would count nodes of the next level too. Theval levelSizekeeps the number from before.nullchecks. The tree usesnullfor missing children, so the code compares with!= nullbefore enqueueing. Anullin the queue would make the code fail with aNullPointerExceptionas soon as it reads a field of it.returninside the method. The earlyreturn result.toListis fine here, because it is not inside a lambda. The final lineresult.toListis the method's value withoutreturn.ArrayBufferversusList.ArrayBuffergrows cheaply at its end with+=. The method promises an immutableList[Int], sotoListconverts it at the end.
Complexity
Time: O(n) for a tree of n nodes. Each node enters the queue once and leaves it once, with 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 level of a complete binary tree can contain around half of all the nodes. The result holds one value per level.
Edge cases and common mistakes
- Empty tree. The early return gives
List(). Without it, the queue would start with anull, and the loop would throw aNullPointerException. - A single node.
[7]givesList(7): the level has one node and it is also the last one. - A level seen only through the left subtree. For
[1,2,null,3,null,4], every node is the only one on its level, and the answer isList(1, 2, 3, 4). Following only right pointers returnsList(1). - Reading
queue.sizeagain inside the inner loop, in the testi == queue.size - 1. The size changes as nodes leave and children join, so the test picks the wrong nodes: on[1,2,3,null,5,null,4]that version returnsList(2, 5). - Recording the first node of each level instead of the last. That gives the left side view:
List(1, 2, 5)for the same tree. - Repeated values. Values may repeat; the code works with nodes, not with values, so duplicates change nothing.
Testing
Trees are written in level order, with null for a missing child.
[1,2,3,null,5,null,4]givesList(1, 3, 4).[1,2,3,4]givesList(1, 3, 4).[]givesList().[1,null,3]givesList(1, 3).[1,2,null,3,null,4]givesList(1, 2, 3, 4).[7]givesList(7).
