Given a modified binary search tree, find k'th smallest element

Suppose in a given binary开发者_JAVA百科 tree if each node contains number of child elements, then what is the optimal way to find k'th smallest element in the tree ?

Please note this is not regular BST. Each node is containing number of child element under it.

find_element(root, k)

    if(root.left.nchildren + 1 == k - 1) 
        return root;

    if(root.left.nchildren + 1 >= k)
        return find_element(root.left, k)             

    else 
        return find_element(root.right, k - (root.left.children + 1))

Traverse BST in InOrder traverse manner and store elements to array. Your array is a sorted array.

This is what I got:

find (root, k)
{
leftChildCount = root->left->n
rightChildCount = root->right->n

if (leftChildCount+1 == k)
  Print root node
else if (k< leftChildCount)
  Find(root->left,k)
else
  Find(root->right,k-leftChildCount)
}