LeetCode Problem #230. Kth Smallest element in Binary Search Tree.

 

Problem Statement:

Given a binary search tree. Program should return Kth Smallest element in the binary search tree.

Suppose if the binary tree is represented as:

3,1,4,null, 2

Then 1st smallest element is 1, second smallest element is 2 and 3rd smallest element is 3.

 

Solution with Explanation:

• The binary tree consists of elements in sorted order.
• The easiest way of finding solution is insert the elements in the priority queue and then  pop out k-1 elements, then top element of the priority queue is the kth smallest element of the tree.
• Optimized solution is doing in-order traversal and keeping track of the count of number of elements visited.
•  After visiting the left most element of the binary tree, increase the count to 1 and traverse back in in-order manner and increase the count.
• Whenever the count is reached to k return that element.

Complexity Explanation:

• As the traversal is in-order, each node is visited only once.
• The traversal continues till the Kth element is found.
• So, the complexity of the above solution is O(K), where k is the kth smallest element asked for.
  

Code in C++

class Solution {
    int Traverse(TreeNode *root, int k, int &iter){
        if(!root)
            return -1;
        int val = Traverse(root->left, k, iter);
        if(val != -1)
            return val;
        ++iter;
        if(iter == k)
            return root->val;
       
        val = Traverse(root->right, k, iter);
       
        return val;
    }
public:
    int kthSmallest(TreeNode* root, int k) {
            int iter  = 0;
        return Traverse(root, k, iter);
    }
};