**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:

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)