Last updated on February 2nd, 2025 at 06:38 am

Here, we see a Kth Smallest Element in a BST LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Binary Search, Tree

Companies

Bloomberg, Google, Uber

Level of Question

Medium

Kth Smallest Element in a BST LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used is Tree Depth First Search (DFS). Specifically:

• Inorder Traversal is used to traverse the tree in sorted order.
• The traversal collects all the node values in a list/array.
• The k-th smallest element is accessed directly from the sorted list.

3. Code Implementation in Different Languages

3.1 Kth Smallest Element in a BST C++

class Solution {
public:
    void preOrderTraversal(TreeNode* root, vector<int> &v){
        if(root == NULL)    return;
        v.push_back(root->val);
        preOrderTraversal(root->left, v);
        preOrderTraversal(root->right, v);      
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> v; 
        preOrderTraversal(root, v);
        sort(v.begin(), v.end());
        return v[k-1];
    }
};

3.2 Kth Smallest Element in a BST Java

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

    private void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        values.add(root.val);
        inorder(root.right);
    }
}

3.3 Kth Smallest Element in a BST JavaScript

var kthSmallest = function(root, k) {
    let vals = [];
    (function dfs(node) {
        if (vals.length !=k) {
        if(node.left) dfs(node.left);
        vals.push(node.val);
        if (node.right) dfs(node.right);
        }  
    })(root)
    return vals[k-1]    
};

3.4 Kth Smallest Element in a BST Python

class Solution(object):
    def kthSmallest(self, root, k):
        values = []
        self.inorder(root, values)
        return values[k - 1]

    def inorder(self, root, values):
        if root is None:
            return
        self.inorder(root.left, values)
        values.append(root.val)
        self.inorder(root.right, values)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n + n log n)	O(n)
Java	O(n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(n)