Kth Smallest Element in BST in DSA Typescript - Execution Trace

Concept Flow - Kth Smallest Element in BST

Start at root node

↓

Traverse left subtree

↓

Visit current node

↓

Count visited nodes

↓

Is count == k?

No→Traverse right subtree

Yes↓

Return current node value

↓

Done

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

Execution Sample

DSA Typescript

function kthSmallest(root, k) {
  let count = 0;
  let result = null;
  function inorder(node) {
    if (!node || result !== null) return;
    inorder(node.left);
    count++;
    if (count === k) { result = node.val; return; }
    inorder(node.right);
  }
  inorder(root);
  return result;
}

This code visits nodes in ascending order and returns the kth smallest value.

Execution Table

Step	Operation	Node Visited	Count	Action	Visual State
1	Start at root	5	0	Traverse left subtree	5 / 3 7
2	Traverse left	3	0	Traverse left subtree	5 / 3 7 / 2 4
3	Traverse left	2	0	Traverse left subtree	5 / 3 7 / 2 4 / 1
4	Visit node	1	1	Count=1, not k=3, traverse right	5 / 3 7 / 2 4 / 1
5	Traverse right	null	1	No node, back to parent	5 / 3 7 / 2 4 / 1
6	Visit node	2	2	Count=2, not k=3, traverse right	5 / 3 7 / 2 4 / 1
7	Traverse right	null	2	No node, back to parent	5 / 3 7 / 2 4 / 1
8	Visit node	3	3	Count=3 equals k, result=3, stop	5 / 3 7 / 2 4 / 1
9	Stop traversal	N/A	3	Return result=3	5 / 3 7 / 2 4 / 1

💡 Count reached k=3 at node with value 3, traversal stops.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	Final
count	0	1	2	3	3
result	null	null	null	3	3
current node	5	1	2	3	3

Key Moments - 3 Insights

Why do we stop traversal immediately after count equals k?

Because once we find the kth smallest node (step 8), continuing traversal is unnecessary and inefficient, as shown in execution_table row 8.

Why do we traverse left subtree first before visiting the current node?

In a BST, left subtree nodes are smaller, so inorder traversal visits nodes in ascending order. This is shown in steps 2 and 3 where we go left before counting.

What happens if the BST has fewer than k nodes?

The traversal finishes without count reaching k, so result remains null, indicating kth smallest does not exist. This is implied by the exit condition in the code.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of count after visiting node 2 (step 6)?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'Count' column at step 6 in execution_table.

At which step does the traversal stop because count equals k?

A Step 4

B Step 8

C Step 6

D Step 9

💡 Hint

Look for the step where 'Count=3 equals k' in the 'Action' column.

If k was 2 instead of 3, at which node would the traversal stop?

A Node 2

B Node 1

C Node 3

D Node 4

💡 Hint

Refer to variable_tracker for count values and nodes visited in order.

Concept Snapshot

Kth Smallest Element in BST:
- Use inorder traversal (left, node, right)
- Count nodes visited in ascending order
- Stop when count == k
- Return current node's value
- Efficient: stops early once kth found

Full Transcript

To find the kth smallest element in a binary search tree, we use inorder traversal which visits nodes in ascending order. We start at the root and go as left as possible, visiting nodes and counting them. When the count reaches k, we stop and return that node's value. This method is efficient because it stops early without visiting all nodes. The execution table shows each step visiting nodes 1, 2, and 3, counting them until the third node is reached, which is the kth smallest for k=3.