# KTH SMALLEST ELEMENT IN TREE

By: Saurav

2018-01-21 02:32:00 UTC

Given a binary search tree, write a function to find the kth smallest element in the tree.

Example :

Input :
2
/ \
1 3

and k = 2

Return : 2

As 2 is the second smallest element in the tree.
NOTE : You may assume 1 <= k <= Total number of nodes in BST

InterviewBit

If you think about it, its a question similar to finding kth smallest element in an array. The best data structure for that case uses a heap of size k. But here its a tree. Either we can convert the tree into a heap or we can create another heap which will take extra space.

Another approach can be to use in order traversal to get all elements up to k in an array and return the last element. We can simply add all elements to the array as well and return the k-1 element. Both have O(n) time complexity.

I will use the latter simpler one:

```  def kthsmallest(a, b)
return nil if !a or b < 0

final_array = Array.new
inorder_k_times(a, final_array)

return final_array[b-1]

end

def inorder_k_times(a, array)

return if !a
inorder_k_times(a.left, array)
array << a.data
inorder_k_times(a.right, array)

end```

Looks good to me.