Finding kth Smallest Element
You'll learn how to efficiently locate the kth smallest element in a Binary Search Tree by leveraging its ordering property.
The Core Idea
Finding the kth smallest element means identifying which node would appear at position k if you listed all BST values in sorted order. For example, the 3rd smallest element is the value that comes third when counting from the smallest value up.
Since inorder traversal of a BST visits nodes in sorted order (left-root-right), we can use it with a counter. As we traverse, we increment a counter at each node. When the counter reaches k, we've found our answer!
The Counter Approach
Think of it like walking through a sorted list and counting: "1st smallest... 2nd smallest... 3rd smallest..." When you reach the kth position, you stop and report that value.
def findKthSmallest(root, k):
# Helper function with counter
def inorder(node, counter):
if node is None:
return None, counter
# Search left subtree first
result, counter = inorder(node.left, counter)
if result is not None:
return result, counter
# Visit current node
counter += 1
if counter == k:
return node.value, counter
# Search right subtree
return inorder(node.right, counter)
result, _ = inorder(root, 0)
return result
The traversal visits nodes in ascending order, counting each one. The moment we hit the kth node during this sorted walk-through, we return its value.
Key Takeaway: Finding the kth smallest element in a BST leverages inorder traversal with a counter, visiting nodes in sorted order until reaching position k—typically O(k + h) time where h is tree height.