Day 20 - Construct Binary Search Tree from Preorder Traversal

Solution.kt

// https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/530/week-3/3305/

/**
 * 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
 * }
 */
class Solution {
    fun bstFromPreorder(preorder: IntArray): TreeNode? {
        return bst(preorder, 0, preorder.size - 1)
    }
    
    fun bst(array: IntArray, a: Int, b: Int): TreeNode? {
        val node = TreeNode(array[a])
        if (a == b) {
            return node
        }
        
        var leftRoot = a + 1
        var rightRoot = b + 1
        
        for (i in a + 1 .. b) {
            if (array[i] > array[a]) {
                rightRoot = i
                break
            }
        }
        
        if (leftRoot != rightRoot) {
            node.left = bst(array, leftRoot, rightRoot - 1)
        }
        if (rightRoot <= b) {
            node.right = bst(array, rightRoot, b)   
        }
        
        return node
    }
}