Kth Smallest Element in BST in DSA Python

Mental Model

A binary search tree keeps values sorted if you look at them in order. To find the kth smallest, we walk through the tree in order and count until we reach k.

Analogy: Imagine a bookshelf where books are arranged from shortest to tallest. To find the kth shortest book, you start from the shortest and count up until you reach the kth one.

      5
     / \
    3   7
   / \   \
  2   4   8
↑root

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, find 3rd smallest element

Goal: Find the 3rd smallest value in the BST by in-order traversal

Step 1: Start at root (5), go left to 3

5 -> [3↑] -> 7 -> 2 -> 4 -> 8

Why: In-order means left subtree first, so we go left to find smaller values

Step 2: Go left from 3 to 2

5 -> 3 -> 7 -> [2↑] -> 4 -> 8

Why: Keep going left to reach smallest values first

Step 3: Visit 2 (count=1), no left child, go back to 3

[2] -> 3 -> 5 -> 7 -> 4 -> 8

Why: 2 is the smallest, count it and move up to parent

Step 4: Visit 3 (count=2), go right to 4

2 -> [3↑] -> 5 -> 7 -> 4 -> 8

Why: After left subtree, visit node then right subtree

Step 5: Visit 4 (count=3), found kth smallest

2 -> 3 -> [4] -> 5 -> 7 -> 8

Why: 4 is the 3rd smallest, stop traversal

Result:

2 -> 3 -> 4 -> 5 -> 7 -> 8
Answer: 4

Annotated Code

DSA Python

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

def kth_smallest(root, k):
    stack = []
    curr = root
    count = 0
    while curr or stack:
        while curr:
            stack.append(curr)  # go left as far as possible
            curr = curr.left
        curr = stack.pop()  # visit node
        count += 1
        if count == k:
            return curr.val  # found kth smallest
        curr = curr.right  # go right subtree

# Driver code
root = TreeNode(5)
root.left = TreeNode(3, TreeNode(2), TreeNode(4))
root.right = TreeNode(7, None, TreeNode(8))

k = 3
result = kth_smallest(root, k)
print(result)

while curr: stack.append(curr) # go left as far as possible curr = curr.left

Traverse left subtree to reach smallest nodes first

curr = stack.pop() # visit node count += 1

Visit node and increment count to track order

if count == k: return curr.val # found kth smallest

Stop traversal when kth smallest is found

curr = curr.right # go right subtree

After visiting node, explore right subtree

Output

4

Complexity Analysis

Time: O(h + k) because we traverse down to the leftmost node (height h) and then visit k nodes in order

Space: O(h) because the stack stores nodes along the path from root to leftmost leaf

vs Alternative: Naive approach is to do full in-order traversal O(n), this stops early after k nodes, saving time

Edge Cases

k is 1 (smallest element)

Returns the leftmost node value correctly

DSA Python

if count == k:
    return curr.val  # found kth smallest

k equals number of nodes (largest element)

Returns the largest node value after full traversal

DSA Python

if count == k:
    return curr.val  # found kth smallest

k is larger than number of nodes

Function returns None implicitly (no kth element)

DSA Python

while curr or stack:

When to Use This Pattern

When you need the kth smallest or largest element in a BST, use in-order traversal with a counter to find it efficiently.

Common Mistakes

Mistake: Not using in-order traversal, so nodes are not visited in sorted order
Fix: Use in-order traversal (left, node, right) to visit nodes in ascending order

Mistake: Not stopping traversal after finding kth element, causing unnecessary work
Fix: Return immediately when count equals k to avoid extra traversal

Summary

Finds the kth smallest value in a binary search tree using in-order traversal.

Use when you want the kth smallest element without sorting all nodes explicitly.

The key is that in-order traversal visits nodes in ascending order, so counting visits finds the kth smallest.

Practice

1. What does the term Kth Smallest Element in BST mean?

easy

A. The element that is the Kth largest in the BST

B. The element that is the Kth in ascending order in the BST

C. The root element of the BST

D. The element with value K in the BST

Solution

1. Step 1: Understand BST ordering

   A Binary Search Tree (BST) stores elements so that left child is smaller and right child is larger.

2. Step 2: Define Kth smallest element

   The Kth smallest element is the element that appears in the Kth position when all elements are sorted ascending.

3. Final Answer:

   The element that is the Kth in ascending order in the BST -> Option B

4. Quick Check:

   Kth smallest means sorted order position [OK]

Hint: Kth smallest means counting nodes in ascending order [OK]

Common Mistakes:

• Confusing Kth smallest with Kth largest
• Thinking it means the root node
• Assuming K is the value, not position

2. Which of the following Python function signatures is correct to find the Kth smallest element in a BST?

easy

A. def kth_smallest(root: Optional[TreeNode], k: int) -> int:

B. def kth_smallest(k: int, root: TreeNode) -> int:

C. def kth_smallest(root: TreeNode, k: str) -> int:

D. def kth_smallest(root: TreeNode) -> int:

Solution

1. Step 1: Check parameter order and types

   The function should take the root node and an integer k to find the Kth smallest element.

2. Step 2: Validate correct typing and order

   def kth_smallest(root: Optional[TreeNode], k: int) -> int: correctly uses root as TreeNode (or Optional) and k as int, returning int.

3. Final Answer:

   def kth_smallest(root: Optional[TreeNode], k: int) -> int: -> Option A

4. Quick Check:

   Correct parameter order and types [OK]

Hint: Root node first, k as int second in function parameters [OK]

Common Mistakes:

• Swapping parameter order
• Using wrong type for k (like string)
• Missing k parameter

3. Given the BST below and k = 3, what is the output of the function kth_smallest(root, 3)?

       5
      / \
     3   7
    / \   \
   2   4   8

medium

A. 4

B. 5

C. 3

D. 7

Solution

1. Step 1: List BST elements in ascending order

   Inorder traversal gives: 2, 3, 4, 5, 7, 8.

2. Step 2: Identify the 3rd smallest element

   The 3rd element in this list is 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Inorder 3rd element = 4 [OK]

Hint: Inorder traversal lists nodes ascending; pick Kth [OK]

Common Mistakes:

• Choosing root or random node instead of Kth
• Counting nodes incorrectly
• Confusing Kth smallest with Kth largest

4. The following code tries to find the Kth smallest element in a BST but has a bug. What is the bug?

def kth_smallest(root, k):
    stack = []
    while True:
        while root:
            stack.append(root)
            root = root.right  # Bug here
        root = stack.pop()
        k -= 1
        if k == 0:
            return root.val
        root = root.left

medium

A. Stack should be initialized with root

B. Return statement is missing

C. k should be incremented, not decremented

D. It should go to the left child first, not right

Solution

1. Step 1: Analyze traversal direction

   For Kth smallest, we do inorder traversal: left -> node -> right. The code wrongly goes right first.

2. Step 2: Identify correct child to traverse first

   It should go to the left child first to get smallest elements first.

3. Final Answer:

   It should go to the left child first, not right -> Option D

4. Quick Check:

   Inorder traversal starts with left child [OK]

Hint: Inorder traversal: always left child first [OK]

Common Mistakes:

• Going right child first in inorder
• Not using stack properly
• Incorrect decrement of k

5. You have a BST with nodes: 10, 5, 15, 3, 7, 12, 18. You want to find the 5th smallest element. Which approach below correctly finds it efficiently?

hard

A. Use preorder traversal and return the 5th node visited

B. Traverse only right subtree and pick the 5th node

C. Perform inorder traversal and return the 5th visited node

D. Return the root node value directly

Solution

1. Step 1: Understand traversal types

   Inorder traversal visits nodes in ascending order in BST.

2. Step 2: Apply inorder traversal to find Kth smallest

   Perform inorder traversal and stop at the 5th node visited to get the 5th smallest element.

3. Final Answer:

   Perform inorder traversal and return the 5th visited node -> Option C

4. Quick Check:

   Inorder traversal gives sorted order [OK]

Hint: Use inorder traversal to get sorted nodes [OK]

Common Mistakes:

• Using preorder or postorder which are not sorted
• Ignoring left subtree nodes
• Assuming root is always Kth smallest