Marc Lester Tan

Tree traversal problems are very common in LC and this easy-level LC problem looks difficult at first but once you find out the pattern, implementing the solution in recursive way is very easy.

import java.util.*

class Solution {
    fun increasingBST(root: TreeNode?): TreeNode? {
        var queue = ArrayDeque<TreeNode>()
        
        fun increasingBST_(root: TreeNode?, queue: ArrayDeque<TreeNode>) {
            if(root == null) return
            
            increasingBST_(root.left, queue)
            queue.offer(root)
            increasingBST_(root.right, queue)
        }
        
        increasingBST_(root, queue)
        
        var root = TreeNode(-1)
        var node = root
        while(!queue.isEmpty()){
            var item = queue.poll()
            node.right = TreeNode(item.`val`)
            node = node.right
        }
        
        return root.right
        
    }
}

Since the problem requires us to travers the tree in in-order, we have search all left nodes first, then root and finally right nodes. As we go along, we collect these nodes in a queue. Finally, loop through the queue and construct our output tree.

Runtime: 220 ms, faster than 100.00% of Kotlin online submissions for Increasing Order Search Tree.
Memory Usage: 35.9 MB, less than 100.00% of Kotlin online submissions for Increasing Order Search Tree.