LeetCode-in-All

230. Kth Smallest Element in a BST

Medium

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1

Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3

Output: 3

Constraints:

• The number of nodes in the tree is n.
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Solution

import com_github_leetcode.TreeNode

/*
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
object Solution {
    var index = 0
    var value = -1

    def kthSmallest(root: TreeNode, k: Int): Int = {
        index = 0
        value = -1
        if (root == null) -1
        else inorder(root, k)
        value
    }

    // Using In order
    def inorder(root: TreeNode, k: Int): Unit = {
        if (root != null && index < k) {
            inorder(root.left, k)
            index += 1
            if (index == k) value = root.value
            inorder(root.right, k)
        }
    }
}

This site is open source. Improve this page.