C++: 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.
 * 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 ans;
    int cnt;

    // InOrder Traversal of the Tree.
    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);
    }
    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!