Skip to content
AI360Xpert
Back to Trees
Medium

Kth Smallest Element in a BST

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

Examples

Input:root = [3,1,4,null,2], k = 1
Output:1
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 <= 10^4
  • 0 <= Node.val <= 10^4

Approach

Perform an inorder traversal (left, root, right) of the BST, which visits nodes in ascending order. Store all the values in an array. Since we want the kth smallest, we simply return the element at index `k - 1` in the array.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(n)

This approach requires visiting all nodes and storing all values, which is O(n) space and time.

Solution.java
class Solution {    public int kthSmallest(TreeNode root, int k) {        List<Integer> list = new ArrayList<>();        inorder(root, list);        return list.get(k - 1);    }        private void inorder(TreeNode root, List<Integer> list) {        if (root == null) return;                inorder(root.left, list);        list.add(root.val);        inorder(root.right, list);    }}