Sign in
Skip to solution
mediumDSA

How do you find the kth smallest element in a BST?

700 views
01

Understand the problem

Explain kth-smallest in a BST.

treesbstinorder
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

An inorder traversal of a BST yields sorted order, so the kth visited node is the answer — stop early once you've counted k. Average O(h + k) using an explicit stack. Augmenting nodes with subtree sizes makes repeated queries O(h).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Iterative in-order, early stop
Run Playground
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def kth_smallest(root, k):
    stack = []
    node = root
    while stack or node:
        while node:                 # dive to the smallest
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right           # then the right subtree
    return None


# --- demo ---
root = TreeNode(5,
    TreeNode(3, TreeNode(2), TreeNode(4)),
    TreeNode(6))
print(kth_smallest(root, 3))   # 4
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 56 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track