Course contentsShow
← Computer Science
Lesson 516 of 2,87212. Binary Search TreesFree lesson

Finding kth Smallest Element

Locate the kth smallest element using inorder traversal with a counter or augmented tree structure.

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.