Kth Smallest Element in BST in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Function

What is the output of the following code when finding the 3rd smallest element in the BST?

DSA Python

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

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

# Construct BST
root = Node(5)
root.left = Node(3)
root.right = Node(7)
root.left.left = Node(2)
root.left.right = Node(4)
root.right.left = Node(6)
root.right.right = Node(8)

print(kth_smallest(root, 3))

A 3

B 5

C 6

D 4

💡 Hint

Remember that inorder traversal of BST gives sorted order.

The inorder traversal of the BST visits nodes in ascending order: 2, 3, 4, 5, 6, 7, 8.

The 3rd smallest element is 4.

🧠 Conceptual

intermediate

Understanding Inorder Traversal in BST

Why does inorder traversal help in finding the kth smallest element in a BST?

A Because inorder traversal visits nodes in descending order of their values.

B Because inorder traversal visits nodes in ascending order of their values.

C Because inorder traversal visits nodes randomly.

D Because inorder traversal visits only leaf nodes.

💡 Hint

Think about the BST property and how inorder traversal works.

Inorder traversal visits the left subtree, then the node, then the right subtree.

In a BST, this order corresponds to ascending order of values.

❓ Predict Output

advanced

Output of Recursive Kth Smallest Function

What is the output of this recursive function to find the 4th smallest element in the BST below?

DSA Python

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

count = 0
def kth_smallest_recursive(root, k):
    global count
    if not root:
        return None
    left = kth_smallest_recursive(root.left, k)
    if left is not None:
        return left
    count += 1
    if count == k:
        return root.val
    return kth_smallest_recursive(root.right, k)

# Construct BST
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.right = Node(18)

print(kth_smallest_recursive(root, 4))

A 10

B 7

C 15

D 5

💡 Hint

Trace the inorder traversal and count nodes visited.

The inorder traversal order is 3, 5, 7, 10, 15, 18.

The 4th smallest element is 10.

🔧 Debug

advanced

Identify the Bug in Kth Smallest Element Code

What error will this code produce when trying to find the 2nd smallest element?

DSA Python

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

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

# Construct BST
root = Node(1)

print(kth_smallest_buggy(root, 2))

A IndexError: pop from empty list

B 2

C 1

D None

💡 Hint

Check what happens when the stack is empty and root is None.

The code pops from stack without checking if stack is empty after traversal.

For this tree, after visiting node 1, root and stack become empty, but loop tries to pop again causing IndexError.

🚀 Application

expert

Number of Nodes Visited to Find Kth Smallest

In a BST with 7 nodes, how many nodes does the iterative kth smallest function visit (pop from stack) to find the 5th smallest element?

A 6

B 7

C 5

D 4

💡 Hint

Think about inorder traversal and how many nodes are popped before reaching the kth.

To find the 5th smallest, the function visits nodes in ascending order.

It pops nodes 1, 2, 3, 4, and 5 in order.

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