Java: Kth Smallest Element in a BST

Thought Process

The problem requires finding the Kth smallest element in a Binary Search Tree (BST). Since a BST's in-order traversal yields elements in ascending order, we can use this property to solve the problem efficiently. We perform an in-order traversal and keep a counter to track the number of nodes visited. When the counter equals k, we have found the Kth smallest element. 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 
class Solution {
    int cnt =0;
    int ans =0;
    public void inOrder(TreeNode root, int k){

        if(root == null)
            return;

        inOrder(root.left,k);
        cnt++;
        if(cnt==k)
            ans = root.val;

        inOrder(root.right,k);

    }
    public int kthSmallest(TreeNode root, int k) {

        inOrder(root,k);
        return ans;
        
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm performs an in-order traversal of the tree, visiting each node once, making it linear in time complexity, where n is the number of nodes in the tree.

Space Complexity: O(h)

The algorithm uses recursion, which consumes stack space proportional to the height of the tree. In the worst case, this is O(n) for a skewed tree.

Code copied!