Solution For Kth Smallest Element In A Bst

Problem Statement:

Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element 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 <= 104

0 <= Node.val <= 104

Solution:

Approach 1: Inorder Traversal of BST

One of the simplest and most intuitive solutions for this problem is to traverse the tree in an inorder fashion. In an inorder traversal of BST, the elements are sorted in ascending order. So, we can traverse the tree in inorder, and maintain a count of the number of nodes that we have visited so far. Once the count becomes equal to k, we have reached the kth smallest element.

Algorithm:

1. Traverse the BST in inorder fashion.
2. While traversing, do the following:
   a. When we visit a node, increment the counter by 1.
   b. If the counter becomes equal to k, return the value of the current node.
3. If we have traversed the entire tree and haven’t found the kth smallest element, return -1.

Time Complexity:

O(n) – We have to traverse the entire tree.

Space Complexity:

O(h) – We are making use of the call stack, which can grow up to h levels, where h is the height of the tree.

Approach 2: Finding the kth Smallest Element Using Binary Search

Another approach to solve this problem is to make use of binary search. We can perform a binary search on the range of values that are present in the BST. We can start with the smallest value in the BST and the largest value in the BST, and find the middle element. We can then find the number of nodes that are smaller than or equal to this middle element. If this number is less than k, we can discard the left half of the range, and repeat the same process on the right half. If this number is greater than or equal to k, we can discard the right half of the range, and repeat the same process on the left half. We can continue performing the binary search until we find the kth smallest element.

Algorithm:

1. Initialize l and r to the minimum and maximum values in the BST, respectively.
2. While l <= r, do the following:
   a. Set mid to (l+r)/2.
   b. Set cnt to the number of nodes that are smaller than or equal to mid.
   c. If cnt < k, set l to mid+1.
   d. If cnt >= k, set r to mid-1.
3. Return l.

Time Complexity:

O(n*log(max_value-min_value)) – We have to perform binary search, which has a time complexity of O(log(max_value-min_value)), where max_value and min_value are the maximum and minimum values in the BST, respectively. We also have to find the number of nodes that are smaller than or equal to a given value, which can be done in O(n) time.

Space Complexity:

O(h) – We are making use of the call stack, which can grow up to h levels, where h is the height of the tree.

Step by Step Implementation For Kth Smallest Element In A Bst

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        //inorder traversal of a BST gives us the elements in sorted order
        List list = new ArrayList<>();
        inorder(root, list);
        return list.get(k-1);
    }
    
    public void inorder(TreeNode root, List list){
        if(root == null) return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}

def kthSmallest(self, root: TreeNode, k: int) -> int:
    
    # Initialize an empty stack
    stack = []
    
    # Push the root node to the stack
    stack.append(root)
    
    # Initialize a count variable to keep track of nodes visited
    count = 0
    
    # Loop until stack is empty
    while stack:
        
        # Pop the top node from the stack
        node = stack.pop()
        
        # If the node has a right child, push it to the stack
        if node.right:
            stack.append(node.right)
        
        # If the node doesn't have a left child, it is a leaf node
        # so increment the count and check if it is the kth smallest node
        if not node.left:
            count += 1
            if count == k:
                return node.val
        
        # If the node has a left child, push it to the stack
        if node.left:
            stack.append(node.left)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    // create an empty array to store all node values
    const nums = [];
    // traverse the tree using in-order traversal
    // this will store the node values in ascending order
    inOrder(root);
    // return the kth element in the array
    return nums[k - 1];
    
    function inOrder(node) {
        // if the node is null, return
        if (!node) return;
        // recursively call inOrder on the left child
        inOrder(node.left);
        // push the node's value into the array
        nums.push(node.val);
        // recursively call inOrder on the right child
        inOrder(node.right);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int count = 0; 
        int result = 0; 
        
        inorder(root, k, count, result); 
        
        return result; 
    }
    
    void inorder(TreeNode* root, int k, int& count, int& result) {
        if (root == nullptr) {
            return; 
        }
        
        inorder(root->left, k, count, result); 
        count++; 
        if (count == k) {
            result = root->val; 
            return; 
        }
        inorder(root->right, k, count, result); 
    }
};

public int KthSmallest(TreeNode root, int k) { 
     // Base Case 
     if (root == null) { 
         return 0; 
     } 
   
     // Create a stack to do iterative inorder traversal 
     Stack st = new Stack(); 
   
     // Initialize current node as root 
     TreeNode curr = root; 
   
     // Traverse the tree 
     while (curr != null || st.Count > 0) { 
   
         /* Reach the left most TreeNode of the 
            curr TreeNode */
         while (curr !=  null) { 
             st.Push(curr); 
             curr = curr.left; 
         } 
   
         /* Current must be NULL at this point */
         curr = st.Pop(); 
   
         // Decrement count by 1 
         k--; 
   
         // If the count becomes zero, return current 
         if (k == 0) { 
             return curr.val; 
         } 
   
         /* Else go to the right subtree */
         curr = curr.right; 
     } 
   
     // If k is still greater than 0, then it is not 
        // possible to find kth smallest element 
     return -1; 
 }