Kth Smallest Element in BST in DSA Python - Execution Trace

Concept Flow - Kth Smallest Element in BST

Start at root

↓

Inorder traversal left subtree

↓

Visit current node

↓

Count nodes visited

↓

Is count == k?

No→Inorder traversal right subtree

Yes↓

Return current node value

↓

Done

We do an inorder traversal of the BST, counting nodes visited. When count reaches k, we return that node's value.

Execution Sample

DSA Python

def kth_smallest(root, k):
    count = 0
    def inorder(node):
        nonlocal count
        if not node:
            return None
        left = inorder(node.left)
        if left is not None:
            return left
        count += 1
        if count == k:
            return node.val
        return inorder(node.right)
    result = inorder(root)
    return result

This code finds the kth smallest element by inorder traversal counting nodes.

Execution Table

Step	Operation	Node Visited	Count	Return Value	Visual State
1	Start at root	5	0	None	5 / \ 3 7 / \ 2 4 8
2	Traverse left subtree	3	0	None	5 / \ 3 7 / \ 2 4 8
3	Traverse left subtree	2	0	None	5 / \ 3 7 / \ 2 4 8
4	Visit node	2	1	None	5 / \ 3 7 / \ 2 4 8
5	Traverse right subtree	None	1	None	5 / \ 3 7 / \ 2 4 8
6	Return to node	3	1	None	5 / \ 3 7 / \ 2 4 8
7	Visit node	3	2	None	5 / \ 3 7 / \ 2 4 8
8	Traverse right subtree	4	2	None	5 / \ 3 7 / \ 2 4 8
9	Visit node	4	3	4	5 / \ 3 7 / \ 2 4 8
10	Return value found	4	3	4	5 / \ 3 7 / \ 2 4 8
11	Stop traversal	None	3	4	5 / \ 3 7 / \ 2 4 8

💡 Count reached k=3 at node with value 4, traversal stops and returns 3rd smallest element value 4

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 9	Final
count	0	1	2	3	3
current node	5	2	3	4	4
return value	None	None	None	4	4

Key Moments - 3 Insights

Why do we return immediately when count == k instead of continuing traversal?

Because the inorder traversal visits nodes in sorted order, once count == k, the kth smallest is found. Continuing would waste time. See execution_table step 10 where return value is set and traversal stops.

Why do we check left subtree first before visiting current node?

Inorder traversal visits left subtree first to get smaller elements before current node. This ensures nodes are counted in ascending order. See execution_table steps 2-6 showing left subtree traversal before visiting node.

What happens if the BST is empty or k is larger than number of nodes?

The traversal returns None because no kth element exists. The code returns None when node is None or traversal finishes without count == k. This is not shown in this example but is handled by the base case in code.

Visual Quiz - 3 Questions

Look at the execution_table, what is the count value after visiting node with value 3?

A 2

B 3

C 1

D None

💡 Hint

Check the 'Count' column at step 7 where node 3 is visited.

At which step does the traversal find the kth smallest element?

A Step 7

B Step 10

C Step 9

D Step 4

💡 Hint

Look at the 'Return Value' column where the value is first set and traversal stops.

If k was 2 instead of 3, what would be the return value at the end?

A 2

B 4

C 3

D None

💡 Hint

Check variable_tracker 'count' and 'return value' for count=2 corresponds to node value 3.

Concept Snapshot

Kth Smallest Element in BST:
- Use inorder traversal (left, node, right)
- Count nodes visited during traversal
- When count == k, return node value
- Stops traversal early once found
- Works because inorder visits nodes in ascending order

Full Transcript

To find the kth smallest element in a BST, we do an inorder traversal which visits nodes in ascending order. We keep a count of nodes visited. When the count reaches k, we return that node's value immediately and stop traversal. The traversal visits left subtree first, then current node, then right subtree. This ensures nodes are counted in sorted order. If the BST is empty or k is too large, the function returns None. The example traced shows visiting nodes 2, 3, and 4 in order, counting up to 3, and returning the 3rd smallest element value 4.

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