Kth Smallest Element in a BST

 

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

  • We are given a binary search tree (BST) and an integer k.
  • We need to find the kth smallest element in the BST.
  • The kth smallest element refers to the element that would appear in the sorted order of the BST if all elements are arranged in ascending order.

2. Analyze the problem: To solve this problem, we can perform an in-order traversal of the BST, keeping track of the elements we visit. As we traverse the BST in an in-order manner, the kth element we encounter will be the kth smallest element in the BST.

3. Design an algorithm: Here is the algorithm to find the kth smallest element in a BST:

  1. Initialize a counter count to 0.
  2. Create a helper function inorder that performs an in-order traversal of the BST.
    • If the current node is not null:
      • Recursively call inorder on the left subtree.
      • Increment the count by 1.
      • If count is equal to k, return the value of the current node.
      • Recursively call inorder on the right subtree.
  3. Invoke the inorder function on the root of the BST.
  4. Return the kth smallest element obtained from the inorder function.

4. Explain your approach: The approach involves performing an in-order traversal of the BST and maintaining a counter count to keep track of the number of nodes visited. As we traverse the BST in an in-order manner, we increment the counter and check if it matches the value of k. If the counter equals k, we return the value of the current node, which corresponds to the kth smallest element in the BST.

5. Write clean and readable code:

python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kthSmallest(root, k):
    def inorder(node):
        nonlocal count
        if node:
            result = inorder(node.left)
            if result is not None:
                return result
            count += 1
            if count == k:
                return node.val
            return inorder(node.right)

    count = 0
    return inorder(root)

6. Test your code:

python
# Test case 1
root1 = TreeNode(3)
root1.left = TreeNode(1)
root1.right = TreeNode(4)
root1.left.right = TreeNode(2)
print(kthSmallest(root1, 1))  # Output: 1

# Test case 2
root2 = TreeNode(5)
root2.left = TreeNode(3)
root2.right = TreeNode(6)
root2.left.left = TreeNode(2)
root2.left.right = TreeNode(4)
root2.left.left.left = TreeNode(1)
print(kthSmallest(root2, 3))  # Output: 3

# Test case 3
root3 = TreeNode(1)
root3.right = TreeNode(2)
print(kthSmallest(root3, 2))  # Output: 2

7. Optimize if necessary: The provided solution has a time complexity of O(k) in the worst case since we need to traverse k nodes in the in-order traversal to find the kth smallest element. If the BST is balanced, the average time complexity is O(log n), where n is the number of nodes in the BST.

8. Handle error cases: The code assumes that the input BST is valid, and k is a positive integer. It does not handle cases where the BST is empty or k is out of the valid range. If the BST is empty, the function will return None.

9. Discuss complexity analysis: The time complexity of the solution is O(k) in the worst case, where k is the input parameter representing the kth smallest element. This is because we perform an in-order traversal until we reach the kth element. If the BST is balanced, the average time complexity is O(log n), where n is the number of nodes in the BST. The space complexity is O(h), where h is the height of the BST, as the recursive function stack space will be occupied during the in-order traversal.

Next Post Previous Post