#57 Medium Time O(H+k) Space O(H) Animated

Kth Smallest Element in a BST

Find the kth smallest element in a BST.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Tree traversal with recursive contracts

Ask each subtree for exactly the information its parent needs, then combine the two answers.

Approach: Iterative Inorder Traversal

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Ask each subtree for exactly the information its parent needs, then combine the two answers.

Common Pitfall

Define the base case before combining left and right subtree results.

Description

Find the kth smallest element in a BST.

Constraints

Time Complexity: O(H+k)
Space Complexity: O(H)

Solution — Iterative Inorder Traversal

TimeO(H+k) SpaceO(H)

Implementation Plan

Translate the invariant into these small, testable moves.

Define what one recursive call returns.
Handle an empty node.
Recurse into children.
Combine the child results at the current node.

def kthSmallest(root, k):
    stack = []
    curr = root
    
    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left
            
        curr = stack.pop()
        k -= 1
        if k == 0:
            return curr.val
            
        curr = curr.right

Validate Binary Search Tree

Construct Binary Tree from Preorder and Inorder Traversal

Kth Smallest Element in a BST

Steps

Description

Constraints

Tags

Solution — Iterative Inorder Traversal