Kth Smallest Element in a BST medium

Problem Statement

Given the root of a binary search tree (BST) and an integer k, return the k^th smallest element in the BST. You can assume k is always valid, 1 ≤ k ≤ total nodes of the BST.

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

Steps and Explanation

The key idea is to leverage the properties of a Binary Search Tree (BST). In a BST, an inorder traversal will visit nodes in ascending order. Therefore, we can perform an inorder traversal and keep track of the elements visited. The k-th element encountered during the inorder traversal is the k-th smallest element.

We'll use an iterative approach for inorder traversal to avoid the overhead of recursion. This involves using a stack to keep track of nodes to visit.

1. Initialization: Create an empty stack stack and initialize a counter count to 0.
2. Iteration: While the stack is not empty or the current node is not None:
   • If the current node is not None: push the node onto the stack and move to its left child (current = current.left). This ensures we process the left subtree first.
   • Otherwise (if the current node is None): pop a node from the stack. This node is the next smallest node in the inorder traversal. Increment the count. If count equals k, this popped node's value is the k-th smallest element, so return its value. Then, move to the right child of the popped node (current = current.right).

Code

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

def kthSmallest(root, k):
    stack = []
    count = 0
    current = root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right
    return -1 # Should not reach here if k is valid

# Example usage
root1 = TreeNode(3)
root1.left = TreeNode(1)
root1.right = TreeNode(4)
root1.left.right = TreeNode(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(root1, 1))  # Output: 1
print(kthSmallest(root2, 3))  # Output: 3

Complexity Analysis

• Time Complexity: O(H + k), where H is the height of the BST. In the worst case (a skewed BST), H can be O(N), where N is the number of nodes. However, for a balanced BST, H is O(log N). The inorder traversal visits at most k nodes.
• Space Complexity: O(H) in the worst case due to the stack used for the iterative inorder traversal. For a balanced BST, this becomes O(log N), and for a skewed BST, it's O(N).