Kth Smallest Element in BST in DSA C++ - Execution Trace

Concept Flow - Kth Smallest Element in BST

Start at root

↓

Traverse left subtree

↓

Visit current node

↓

Count visited nodes

↓

Is count == k?

No→Traverse right subtree

Yes↓

Return current node value

We go left as far as possible, visit nodes in ascending order, count them, and stop when we reach the kth node.

Execution Sample

DSA C++

int count = 0;
int kthSmallest(TreeNode* root, int k) {
  if (!root) return -1;
  int left = kthSmallest(root->left, k);
  if (left != -1) return left;
  count++;
  if (count == k) return root->val;
  return kthSmallest(root->right, k);
}

This code finds the kth smallest value in a BST by in-order traversal counting nodes.

Execution Table

Step	Operation	Nodes Visited Count	Current Node	Visual State (In-order visited)
1	Start at root (5)	0	5	[]
2	Traverse left subtree (3)	0	3	[]
3	Traverse left subtree (2)	0	2	[]
4	Traverse left subtree (1)	0	1	[]
5	Visit node 1	1	1	[1]
6	Back to node 2	1	2	[1]
7	Visit node 2	2	2	[1, 2]
8	Traverse right subtree of 2 (null)	2	null	[1, 2]
9	Back to node 3	2	3	[1, 2]
10	Visit node 3	3	3	[1, 2, 3]

💡 Traversal stops when count reaches k=3 at node with value 3.

Variable Tracker

Variable	Start	After Step 5	After Step 7	After Step 10	Final
count	0	1	2	3	3
current node	5	1	2	3	3
k	3	3	3	3	3

Key Moments - 3 Insights

Why do we return immediately when left subtree returns a value?

Because the kth smallest element is found in the left subtree, no need to continue traversal (see step 10 in execution_table).

Why do we increment count after visiting a node?

Because in-order traversal visits nodes in ascending order, counting nodes helps identify when we reach the kth smallest (see count changes in variable_tracker).

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

The function returns -1 indicating no kth smallest element found (not shown in execution_table but handled by base case).

Visual Quiz - 3 Questions

Look at the execution_table, what is the count after visiting node 2 at step 7?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Nodes Visited Count' column at step 7 in execution_table.

At which step does the traversal stop because kth smallest is found?

A Step 17

B Step 14

C Step 10

D Step 5

💡 Hint

Step 10 shows visit node 3 with Nodes Visited Count 3 (k=3) in execution_table.

If k was 5 instead of 3, what would be the count at step 14?

A 5

B 4

C 3

D 6

💡 Hint

In-order visits nodes in ascending order: 1(1st), 2(2nd), 3(3rd), 4(4th), 5(5th).

Concept Snapshot

Kth Smallest Element in BST:
- Use in-order traversal (left, node, right)
- Keep count of visited nodes
- When count == k, return node value
- Stops traversal early when found
- Handles empty tree by returning -1

Full Transcript

To find the kth smallest element in a binary search tree, we do an in-order traversal which visits nodes in ascending order. We keep a count of how many nodes we have visited. When the count matches k, we return the current node's value. The traversal stops immediately after finding the kth node to save time. If the tree is empty or k is too large, the function returns -1. This method ensures we get the kth smallest element efficiently by leveraging the BST property.