Kth Smallest Integer in BST

NeetCode: Kth Smallest Integer in BST · LeetCode: 230. Kth Smallest Integer in BST · Difficulty: Medium

Given a BST and an integer k (1-indexed), return the k-th smallest value. k is at least 1 and at most the number of nodes.

Example

Text

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

Trees are given in LeetCode's level-order array form: the root first, then each level from left to right, with null marking a missing node, so [1, 2, 3, 4, 5] is the tree above. The tree(Integer... values) helper in each program builds a TreeNode from such an array by filling children from a queue. TreeNode has the fields val, left, and right. A missing child is null: Java object references are nullable and the fields are mutable, so no wrapper type is needed.

Brute force: inorder into a list

An inorder traversal (left, node, right) of a BST yields the values in sorted order. Collect them all and index the k-th.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> values = new ArrayList<>();
        inorder(root, values);
        return values.get(k - 1);
    }

    private void inorder(TreeNode node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = tree(5, 3, 6, 2, 4, null, null, 1);
        System.out.println(new Solution().kthSmallest(root, 3));
        System.out.println(new Solution().kthSmallest(root, 1));
    }
}

Output

3
1

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

Optimal: iterative inorder that stops at k

Run the same traversal with an explicit stack (an ArrayDeque used with push and pop), and stop the moment the k-th value is produced. Only the path to the answer is explored, so the cost is O(h + k).

Java

import java.util.ArrayDeque;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (true) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop(); // throws NoSuchElementException if k exceeds the node count
            k--;
            if (k == 0) return node.val;
            cur = node.right;
        }
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = tree(5, 3, 6, 2, 4, null, null, 1);
        System.out.println(new Solution().kthSmallest(root, 3));
        System.out.println(new Solution().kthSmallest(root, 1));
        System.out.println(new Solution().kthSmallest(root, 6));
    }
}

Output

3
1
6

Time: O(h + k). Space: O(h).