Kth Smallest Element in a BST

▶

Steps

setup

Initialize stack and current pointer

We start with an empty stack and set current to the root node (value 3). The count of visited nodes is zero.

💡 Initialization sets up the data structures needed for iterative in-order traversal.

Line:

stack = []
current = root
count = 0

💡 The traversal will begin from the root, and the stack will help us backtrack after reaching leftmost nodes.

fill_cells

Push current node (3) onto stack and move left

Current node 3 is pushed onto the stack. We move current pointer to its left child (node 1).

💡 Pushing nodes onto the stack delays visiting them until their left subtree is fully explored.

Line:

while current:
    stack.append(current)
    current = current.left

💡 Stack keeps track of nodes to visit after left descendants are processed.

fill_cells

Push current node (1) onto stack and move left

Current node 1 is pushed onto the stack. We move current pointer to its left child, which is null.

💡 When current becomes null, it means we reached the leftmost node of this path.

Line:

while current:
    stack.append(current)
    current = current.left

💡 Reaching null signals no more left children; time to visit nodes from stack.

traverse

Pop node (1) from stack and visit it

Current is null, so we pop node 1 from the stack to visit it. Count increments to 1.

💡 Visiting a node means processing it after all left descendants are done.

Line:

current = stack.pop()
count += 1

💡 The first visited node in in-order traversal is the smallest node in the BST.

compare

Check if count equals k

Count is 1, which equals k=1. The algorithm returns the current node's value 1 as the kth smallest element.

💡 The stopping condition ensures we return the correct kth smallest value immediately.

Line:

if count == k:
    return current.val

💡 The algorithm stops as soon as the kth smallest node is visited, optimizing performance.

reconstruct

Return the kth smallest element

The algorithm returns 1 as the kth smallest element and terminates.

💡 Returning the value completes the search and provides the final answer.

Line:

return current.val

💡 The traversal does not continue after finding the kth smallest, saving time.

prune

Additional step: Explanation of why traversal stops early

Since k=1, the algorithm stops after visiting the first node in in-order traversal, which is the smallest element.

💡 Early stopping is a key optimization in kth smallest element search.

Line:

if count == k:
    return current.val

💡 Traversal does not need to visit all nodes, saving time especially in large BSTs.

expand

Hypothetical continuation if k was larger: move to right child

If count was less than k, the algorithm would move current pointer to the right child of the popped node to continue traversal.

💡 Moving to right child explores nodes greater than the current node in in-order traversal.

Line:

current = current.right

💡 Traversal order is left → node → right, so right subtree is visited after node.

fill_cells

Hypothetical push of right child (4) onto stack

If traversal continued, current node 4 would be pushed onto the stack and traversal would move left to node 2.

💡 Pushing right child nodes onto stack continues the in-order traversal pattern.

Line:

while current:
    stack.append(current)
    current = current.left

💡 Left children of right subtree are visited before the right subtree root.

reconstruct

Summary: In-order traversal visits nodes in ascending order

The in-order traversal order for this BST is [1, 2, 3, 4]. The algorithm visits nodes in this order, counting until it reaches k.

💡 Understanding this order is key to grasping why in-order traversal finds the kth smallest element.

💡 In-order traversal of BST yields sorted node values, enabling direct access to kth smallest by counting visits.

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []  # STEP 1: Initialize empty stack
    current = root  # STEP 1: Start at root
    count = 0  # STEP 1: Initialize count

    while current or stack:  # STEP 2: Continue while nodes remain
        while current:  # STEP 3: Push all left children
            stack.append(current)  # STEP 3: Push current
            current = current.left  # STEP 3: Move left
        current = stack.pop()  # STEP 4: Pop from stack
        count += 1  # STEP 4: Increment count
        if count == k:  # STEP 5: Check if kth smallest
            return current.val  # STEP 5: Return value
        current = current.right  # STEP 6: Move to right child

# Driver code
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(1)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    print(kthSmallest(root, 1))  # Output: 1

📊

Kth Smallest Element in a BST - Watch the Algorithm Execute, Step by Step

Watching each stack operation and pointer movement reveals how in-order traversal naturally visits nodes in ascending order, making it the fastest way to understand the kth smallest element search.

Current node: 1

3124

Current node: 2

3124

3124

Current node: 2

3124

Result: [1]

Current node: 2

3124

Result: [1]

Return: 1

3124

Result: [1]

Return: 1

3124

Result: [1]

Return: 1

Current node: 5

3124

Result: [1]

Return: 1

3124

Result: [1]

Return: 1

3124

Result: [1, 2, 3, 4]

Return: 1

Key Takeaways

✓ In-order traversal visits BST nodes in ascending order, enabling direct access to the kth smallest element by counting visits.

This insight is hard to see from code alone because the traversal order and counting are implicit; visualization makes it explicit.

✓ The stack stores nodes whose left subtrees are fully explored but whose right subtrees are yet to be visited, enabling backtracking.

Understanding the stack's role clarifies how iterative traversal mimics recursion.

✓ The algorithm stops immediately when the kth smallest node is visited, optimizing performance by avoiding unnecessary traversal.

This early stopping is subtle in code but critical for efficiency, and visualization highlights this decision clearly.

Practice

1. Consider the following code for computing the range sum of a BST. Given the BST with root value 10, left child 5, right child 15, and range [7, 15], what is the final value of total returned by rangeSumBST?

easy

A. 25

B. 15

C. 40

D. 30

Solution

1. Step 1: Trace initial stack and total

   Start with stack=[10], total=0.

2. Step 2: Pop 10 (in range), add 10, push left(5) and right(15)

   total=10, stack=[5,15]

3. Step 3: Pop 15 (in range), add 15, push left(null) and right(null)

   total=25, stack=[5,null,null]

4. Step 4: Pop null (skip), then pop null (skip), then pop 5 (less than low=7), push right(null)

   total=25, stack=[null]

5. Step 5: Pop null (skip), stack empty, return total=25

   5 is less than low, so it is skipped and not added.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Sum includes 10 and 15 only, total=25 [OK]

Hint: Only nodes within [7,15] add to total [OK]

Common Mistakes:

• Adding nodes outside range
• Forgetting to push children after adding node

2. Given the following code for trimming a BST and the input tree with root value 3, left child 1, right child 4, and low=2, high=3, what is the value of the root node after trimming?

easy

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: Move root to valid range

   Root=3 is within [2,3], so no change.

2. Step 2: Trim left subtree

   Left child=1 < 2, so replace left child with its right subtree (None). Left child becomes None.

3. Step 3: Trim right subtree

   Right child=4 > 3, so replace right child with its left subtree (None). Right child becomes None.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Root remains 3 with no children after trimming [OK]

Hint: Check root adjustment before subtree trimming [OK]

Common Mistakes:

• Assuming root changes when already in range
• Forgetting to trim subtrees correctly

3. Consider the following code snippet implementing the optimal approach for Two Sum IV in BST. Given the BST with nodes [5,3,6,2,4,null,7] and target k=9, what is the value of variable s during the first iteration of the while loop?

easy

A. 9

B. 5

C. 11

D. 7

Solution

1. Step 1: Perform inorder traversal

   Inorder traversal of BST yields sorted array: [2, 3, 4, 5, 6, 7]

2. Step 2: Calculate s in first iteration

   left=0 (value=2), right=5 (value=7), s = 2 + 7 = 9

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum matches target k=9 on first iteration [OK]

Hint: Inorder array first + last sum equals target [OK]

Common Mistakes:

• Off-by-one error in indexing left or right
• Confusing node values with indices
• Miscomputing sum s

4. Consider the following Python code implementing BST validation using inorder traversal. What is the output of the program when run with the given test cases?

easy

A. true followed by false

B. true followed by true

C. false followed by true

D. false followed by false

Solution

1. Step 1: Trace first tree (2,1,3)

   Inorder traversal yields [1,2,3], strictly increasing, so returns true.

2. Step 2: Trace second tree (5,1,4 with children 3 and 6)

   Inorder traversal yields [1,5,3,4,6], 3 < 5 violates BST property, so returns false.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First tree valid BST, second invalid due to subtree violation [OK]

Hint: Inorder traversal must be strictly increasing [OK]

Common Mistakes:

• Assuming subtree root comparison is enough
• Confusing output order
• Missing strict inequality check

5. The following code attempts to compute the range sum of a BST using iterative DFS with pruning. Identify the line containing the subtle bug that causes incorrect results or inefficiency.

medium

A. Line that appends node.left when node.val < low

B. Line that pops node from stack

C. Line that adds node.val to total

D. Line that appends node.right when node.val is in range

Solution

1. Step 1: Understand pruning logic

   If node.val < low, left subtree nodes are smaller and cannot be in range, so left subtree should be skipped.

2. Step 2: Identify incorrect line

   Appending node.left when node.val < low causes unnecessary traversal of left subtree, violating pruning. It should append node.right instead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct pruning requires appending node.right only when node.val < low [OK]

Hint: Prune left subtree if node.val < low [OK]

Common Mistakes:

• Appending wrong subtree when pruning
• Forgetting to check null nodes