LeetCode #230: Kth Smallest Element in a BST

LeetCode Solutions

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

Given a binary search tree, the goal is to find the kth smallest element in the tree.

Algorithm:

  1. Initialize an empty priority queue.
  2. Define a recursive function traverse to traverse the BST in pre-order.
  3. For each node, push its value into the priority queue.
  4. Continue the pre-order traversal on the left and right subtrees.
  5. Return the kth smallest element in the priority queue.

Python Solution:

import heapq

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        pq = []
        def traverse(root):
            if not root:
                return
            heapq.heappush(pq, root.val)
            traverse(root.left)
            traverse(root.right)
            return
        traverse(root)
        return heapq.nsmallest(k, pq)[-1]

We start by initializing an empty priority queue pq. We then define a recursive function traverse that takes in the current node as an argument. If the current node is None, we simply return. Otherwise, we push the node’s value into the priority queue using the heappush method. We then continue the pre-order traversal on the left and right subtrees by recursively calling the traverse function. Finally, we return the kth smallest element in the priority queue using the nsmallest method.

Time and Space Complexity

The time complexity of this solution is O(nlogn), where n is the number of nodes in the tree, since we push each node’s value into the priority queue and retrieve the kth smallest element using the nsmallest method. The space complexity of this solution is also O(n), since the priority queue can potentially store all n nodes in the tree. Therefore, this solution is not as space-efficient as it could be, but it still provides a relatively fast time complexity for finding the kth smallest element in a BST.