Kth Smallest in a BST

Interview Problem Interview Medium Binary Search Tree Stack Depth-first Search

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.kthSmallest(root, k). Return the kth smallest node value in the BST, where k is one-based.

Starter code

class Solution:
    def kthSmallest(self, root, k):
        pass

Test cases

first

{
  "args": [
    {
      "$type": "binary-tree",
      "values": [
        3,
        1,
        4,
        null,
        2
      ]
    },
    1
  ]
}

Expected: 1

Wizard outline

Step 1: Initialize Solution.kthSmallest
Replace the empty starter with the first real state owned by Solution.kthSmallest. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Leftmost Value case
Complete the readable core algorithm for one representative Interview case. Use a stack to produce BST values in ascending inorder sequence.
Step 4: Harden the Third boundary
Repair the reviewed boundary and pass the complete submission contract. BST inorder traversal yields values in strictly ascending order. The algorithm reproduces that order exactly, so the node popped when k reaches zero is the kth smallest.

Footguns and prerequisites

k is one-based; decrement when popping a visited node, not when pushing it.
trees and graphs

Reviewed references

LeetCode 230 — Kth Smallest Element in a BST

Practice prerequisites

Carry State Through Tree DFS(opens in a new tab)
Carry State Through Tree DFS isolates the running total passed to a node equals the sum from the root through that node, independent of sibling branches. That focused state discipline is required when implementing kth smallest bst as a complete Interview Problem.

Recommended approach and implementation

Iteratively push the entire left spine, pop the next inorder node, decrement k, and continue from its right child.

Why it works: BST inorder traversal yields values in strictly ascending order. The algorithm reproduces that order exactly, so the node popped when k reaches zero is the kth smallest.

class Solution:
    def kthSmallest(self, root, k):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        stack = []
        current = root
        while True:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            k -= 1
            if k == 0: return current.val
            current = current.right