A-057● Day 572026.07.03mediumleetcode #230neetcode150

Kth Smallest Element in a BST

#tree#depth-first-search#binary-search-tree#binary-tree

↗ leetcode #230 · kth-smallest-element-in-a-bst

Problem

· problem

P.057

Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

constraints

· 1 ≤ k ≤ n ≤ 10⁴
· 0 ≤ Node.val ≤ 10⁴

// paraphrased summary — see source for full text

examples

example 1input → output

[3,1,4,null,2]
1

example 2input → output

[5,3,6,2,4,null,null,1]
3

Pre-solve

· pre-solve

● 1list shown→● 2select→● 3reveal

☐
What does '1-indexed' mean in this problem?
☐
Can there be duplicate values in the BST?
☐
Is the tree always a valid BST?
☐
Does the solution need to modify the tree structure?
☐
Should we find the kth largest element instead?
☐
Is the tree always perfectly balanced?

check the items you would ask, then press confirm

// session-only state — refresh resets (repeatable practice)

Logic Structure

· logic

● 1slots shown→● 2pick per slot→● 3reveal

// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.

step 1· Initialize stack

○

stack = []

○

stack = [root]

○

stack = {}

step 2· Main loop condition

○

while stack or curr:

○

while curr:

○

while stack:

step 3· Traverse to leftmost node│ │ nested

○

curr = curr.left

○

curr = curr.right

○

while curr: k -= 1

step 4· Pop node from stack│ nested

○

curr = stack.pop()

○

curr = stack[0]

○

stack.pop()

step 5· Check if kth element found│ │ nested

○

if k == 0:

○

if k == 1:

○

if k < 0:

step 6· Move to right subtree│ nested

○

curr = curr.right

○

curr = curr.left

○

stack.append(curr.right)

pick one option per slot

// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.

Solve · Trace

· solve

solution.py

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def kthSmallest(self, root: TreeNode, k: int) -> int:

        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

mental dry-run cases

// walk each case in your head; expand the worked example below if stuck.

case 1

[3,1,4,null,2]
1

→

case 2

[5,3,6,2,4,null,null,1]
3

→

// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.