Kth smallest Element in BST

Kth smallest Element in BST

  September 11, 2017    

---

Explanation :

One approach is to do tree traversal and save elements in Heap and pop kth element but it will require O(n) time and space 

Another approach is to check if k== elements in left subtree +1 then it is root element
Else if k<elements in left subtree then recur for left subtree
Else if k> elements in left subtree then recur for right subtree and decrement k by all the left subtree elements and root.

But the thing is , leftsubtree node should be pre calculted.


Code:

int KthsmallestBst(Node root,int k)
{
int min=-1;
while(root!=null)
{
if(k==root.lcount+1)
return root.data;
if(k<root.lcount)
{
root=root.left;
}
if(k>root.lcount)
{
root=root.right;
k=k-root.lcount-1;
}
}
return min;
}

Approach 3 when we dont have info about left subtree's count.

Use Morris Inorder Traversal http://hackerranksolutionc.blogspot.com/2017/09/morris-inorder-traversal.html

Here we will count the nodes visited in inorder and whenever count==k print node

Code:

Node KthsmallestmorrisInorder(Node root,int k)
{
if(root==null)
return;
int count=0;
Node curr=root;
while(curr!=null)
{
//tree has no left subtree so move to right
if(curr.left==null)
{
++count;
if(count==k)
return curr;
curr=curr.right;
}
else
{
//find preorder suceesor to link with its root
Node pre=curr.left;
while(pre.right!=null || pre.right==curr)
pre=pre.right;
//we have already traversed this tree so remove link and move to right subtree
if(pre.right==curr)
{
pre.right=null;
++count;
if(count==k)
return curr;
curr=curr.right;
}
else {
//link child's right
pre.right=curr;
curr=curr.left;
}
}
}
}