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.


Let me know what you think!
twitter: sprakash24oct
linkedin

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