Marc Lester Tan

Here’s one of my favorite questions in LC. I like this because it looks complicated as it may seem but the approach to the solution is very simple.

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */

import java.util.*

class Solution {
    fun rightSideView(root: TreeNode?): List<Int> {
        if(root == null) return emptyList()
        var queue = ArrayDeque<TreeNode>()
        var level = ArrayDeque<Int>()
        var map = TreeMap<Int, ArrayList<TreeNode>>()
        queue.offer(root)
        level.offer(0)
        
        while(!queue.isEmpty()){
            var node = queue.poll()
            var l = level.poll()
            if(!map.containsKey(l)){
                map[l] = ArrayList<TreeNode>()
            }
            
            map.get(l)?.add(node)
            
            if(node.left != null){
                queue.offer(node.left)
                level.offer(l + 1)
            }
            
            if(node.right != null){
                queue.offer(node.right)
                level.offer(l + 1)
            }
        }
        
        return map.map { it.value.last().`val` }
    }
}

Runtime: 188 ms, faster than 20.59% of Kotlin online submissions for Binary Tree Right Side View.
Memory Usage: 33.8 MB, less than 100.00% of Kotlin online submissions for Binary Tree Right Side View.

In order to figure out the right-side view of the tree, we collect the nodes level by level. Once done, we iterate each level and just retrieve the last element in the list of collected nodes per level.

To do this, we need to do breadth-first traversal on the tree and collect the nodes in a queue. At the same time, we assign a score or level to each of the nodes. If they fall on the same level, then we collect them in a list.

Finally, traverse the tree map and output the result list.