Kth Smallest Element In A Bst - Leetcode Solution

Problem Statement:

Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.

Example 1:

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

Output: 1

Example 2:

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

Output: 3

Constraints:

The number of nodes in the tree is n.

1 <= k <= n <= 104

0 <= Node.val <= 104

Solution:

Approach 1: Inorder Traversal of BST

One of the simplest and most intuitive solutions for this problem is to traverse the tree in an inorder fashion. In an inorder traversal of BST, the elements are sorted in ascending order. So, we can traverse the tree in inorder, and maintain a count of the number of nodes that we have visited so far. Once the count becomes equal to k, we have reached the kth smallest element.

Algorithm:

1. Traverse the BST in inorder fashion.
2. While traversing, do the following: a. When we visit a node, increment the counter by 1. b. If the counter becomes equal to k, return the value of the current node.
3. If we have traversed the entire tree and haven’t found the kth smallest element, return -1.

Time Complexity:

O(n) - We have to traverse the entire tree.

Space Complexity:

O(h) - We are making use of the call stack, which can grow up to h levels, where h is the height of the tree.

Approach 2: Finding the kth Smallest Element Using Binary Search

Another approach to solve this problem is to make use of binary search. We can perform a binary search on the range of values that are present in the BST. We can start with the smallest value in the BST and the largest value in the BST, and find the middle element. We can then find the number of nodes that are smaller than or equal to this middle element. If this number is less than k, we can discard the left half of the range, and repeat the same process on the right half. If this number is greater than or equal to k, we can discard the right half of the range, and repeat the same process on the left half. We can continue performing the binary search until we find the kth smallest element.

Algorithm:

1. Initialize l and r to the minimum and maximum values in the BST, respectively.
2. While l <= r, do the following: a. Set mid to (l+r)/2. b. Set cnt to the number of nodes that are smaller than or equal to mid. c. If cnt < k, set l to mid+1. d. If cnt >= k, set r to mid-1.
3. Return l.

Time Complexity:

O(n*log(max_value-min_value)) - We have to perform binary search, which has a time complexity of O(log(max_value-min_value)), where max_value and min_value are the maximum and minimum values in the BST, respectively. We also have to find the number of nodes that are smaller than or equal to a given value, which can be done in O(n) time.

Space Complexity:

O(h) - We are making use of the call stack, which can grow up to h levels, where h is the height of the tree.

1