0230.md

230. Kth Smallest Element in a BST

Level:

Topic:

Question

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.

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

Intuition

Recursive:

• inorder traversal of a BST is in sorted order
• so at kth root node, return

Code

Time: O(n)
Space: O(n)

Recursive

int K = 0;
int ans = -1;
public int kthSmallest(TreeNode root, int k) {
    K = k;
    inorder(root);
    return ans;
}

private void inorder(TreeNode root) {
    if (root == null)
        return;
    inorder(root.left);
    K--;
    if (K == 0) {
        ans = root.val;
        return;
    }
    inorder(root.right);
}