Binary Tree Level Order Traversal II

Today, we’re going to solve a variation of the Binary Tree Level Order Traversal.

This easy problem can be solved by Breadth-First-Search traversal which is the most straightforward way or we can also use Depth-First-Search traversal.

Using BFS

For BFS, the idea is to traverse the nodes one level at a time. We’re going to collect the nodes along the way and once done processing a particular level, we’re gonna add the collected nodes into another list. Since the problem requires the output to be in reverse, we can use a LinkedList so that we could always insert the newly collected nodes at the beginning of the resulting list with O(1) performance.

class Solution {
    fun levelOrderBottom(root: TreeNode?): List<List<Int>> {
        val res = LinkedList<MutableList<Int>>()
        if(root == null) return res
        
        val queue = ArrayDeque<TreeNode>()
        queue.add(root)
        
        while(queue.isNotEmpty()){
            val n = queue.size
            val temp = mutableListOf<Int>()
            repeat(n){
                val curr = queue.poll()
                temp.add(curr.`val`)

                curr.left?.let { queue.add(it) }
                curr.right?.let { queue.add(it) }                
            }            
            
            res.addFirst(temp)
        }
        
        return res.toList()   
    }
}

Runtime: 188 ms
Memory Usage: 34.5 MB

Time complexity is O(n) where $$n = num of nodes$$

Using DFS

With DFS, we need to write a recursive function that will traverse the nodes as deep as possible. We’re gonna collect the nodes as we go along and put them into their respective buckets. As we go deeper into the tree, we also increment the depth variable so that we can put the nodes into the correct bucket.

class Solution {
    fun levelOrderBottom(root: TreeNode?): List<List<Int>> {
        if(root == null) return emptyList()
        val map = mutableMapOf<Int, MutableList<Int>>()
        var maxDepth = 0
        
        fun helper(node: TreeNode, depth: Int) {
            maxDepth = maxOf(maxDepth, depth)
            if(depth !in map) map[depth] = mutableListOf<Int>()
            
            map[depth]?.add(node.`val`)
            
            node.left?.let { helper(it, depth + 1) }
            node.right?.let { helper(it, depth + 1) }
        }
        
        helper(root, 0)
        val res = mutableListOf<List<Int>>()
        
        (maxDepth downTo 0).forEach {
            res.add(map[it]!!)
        }
        
        return res 
    }
}

Runtime: 360 ms
Memory Usage: 37.1 MB

Time complexity is O(n) where $$n = num of nodes$$

Marc Lester Tan

Using BFS

Using DFS