Kth Smallest Element in a BST

MEDIUM

Description

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.

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 <= 10⁴
0 <= Node.val <= 10⁴

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?

Approaches

Checkout 3 different approaches to solve Kth Smallest Element in a BST. Click on different approaches to view the approach and algorithm in detail.

Inorder Traversal with Array

This approach uses inorder traversal to store all elements in an array and then returns the kth element.

Algorithm

Create a list to store elements
Perform inorder traversal:
- Recursively traverse left subtree
- Add current node value to list
- Recursively traverse right subtree
Return the (k-1)th element from the list

In this approach, we perform an inorder traversal of the BST and store all elements in an array. Since inorder traversal of a BST visits nodes in ascending order, we can simply return the (k-1)th element from the array.

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

Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the treeSpace Complexity: O(n) to store all elements in the array

Pros and Cons

Pros:

Simple to implement
Easy to understand
Can be used when k is not known beforehand

Cons:

Uses extra space to store all elements
Processes all nodes even when k is small
Not efficient for large trees when k is small

Code Solutions

Checking out 3 solutions in different languages for Kth Smallest Element in a BST. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Kth Smallest Element in a BST

Algorithms:

Depth-First Search

Data Structures:

TreeBinary TreeBinary Search Tree

Companies:

Agoda |Cisco |Google |Oracle |