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

Question

Suppose in a given binary tree , if each node contains the number of children , then what is the best way to find the k'th smallest element in the tree?

Please note that this is not an ordinary BST. Each node contains the number of a child below it.

Answer 1

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)) 

Answer 2

Here 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) } 

Answer 3

Move BST to InOrder , and save the elements of the array. Your array is a sorted array.