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

Example 1:

Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \   2 Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Constraints:

  • The number of elements of the BST is between 1 to 10^4.
  • You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Solution

As we know that, Inorder traversal of BST will give elements in sorted order. Do traverse inorder and maintain count, Once count is qual to the k, stop exploring the rest of nodes.

Code

Complexity Analysis

Time complexity: O(k).
Space Complexity: O(1).

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *