2018-01-21 02:32:00 UTC
Given a binary search tree, write a function to find the kth smallest element in the tree.
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
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
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 :)