Find k-th smallest element in BST (Order Statistics in BST)

Solution Approach:

By using In order traversal of BST retrieves elements of tree in the sorted order. The in order traversal uses stack to store to be explored nodes of tree (threaded tree avoids stack and recursion for traversal). The idea is to keep track of popped elements which participate in the order statics.

Implementation:

public int kthSmallest(TreeNode root, int k) 

{

    Stack<TreeNode> stack = new Stack<TreeNode>();

 

    TreeNode p = root;

    int res = 0;

 

    while(!stack.isEmpty() || p!=null)

{

        if(p!=null)

{

            stack.push(p);

            p = p.left;

        }

else

{

            TreeNode t = stack.pop();

            k--;

            if(k==0)

                res = t.val;

            p = t.right;

        }

    }

 

    return res;

}

We can in order traverse the tree and get the kth smallest element. 

Time complexity: O(n) where n is total nodes in tree.