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.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

03

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

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.