Kth Smallest Element in BST in DSA Javascript - 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 Javascript

function kthSmallest(root, k) {
  let count = 0, 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 finds the kth smallest value in a BST by visiting nodes in ascending order.

Execution Table

Step	Operation	Current Node	Count	Result	Visual State
1	Start at root	5	0	null	5 / \ 3 7 / \ 2 4 8
2	Traverse left	3	0	null	5 / \ 3 7 / \ 2 4 8
3	Traverse left	2	0	null	5 / \ 3 7 / \ 2 4 8
4	Visit node	2	1	null	5 / \ 3 7 / \ 2 4 8
5	Traverse right (null)	null	1	null	5 / \ 3 7 / \ 2 4 8
6	Back to node	3	1	null	5 / \ 3 7 / \ 2 4 8
7	Visit node	3	2	null	5 / \ 3 7 / \ 2 4 8
8	Traverse right	4	2	null	5 / \ 3 7 / \ 2 4 8
9	Visit node	4	3	4	5 / \ 3 7 / \ 2 4 8
10	Stop traversal	null	3	4	5 / \ 3 7 / \ 2 4 8

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

Variable Tracker

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

Key Moments - 3 Insights

Why do we stop traversal immediately after finding the kth smallest element?

Because once count equals k (see step 9 in execution_table), we have found the kth smallest node, so continuing traversal is unnecessary and avoided by checking result !== null.

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 (see steps 2 and 3 before visiting nodes).

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 (not shown in this example).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of count at step 7?

A 2

B 1

C 3

D 0

💡 Hint

Check the 'Count' column in execution_table row for step 7.

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

A Step 4

B Step 7

C Step 9

D Step 10

💡 Hint

Look for when 'Result' changes from null to a value in execution_table.

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

A 2

B 3

C 4

D null

💡 Hint

Check variable_tracker for count and result values at steps before step 9.

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 for BST due to sorted order

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 far left as possible, visiting nodes and counting them. When the count reaches k, we stop and return that node's value. This method leverages the BST property that left children are smaller and right children are larger. The traversal stops early once the kth element is found to save time. If the tree has fewer than k nodes, the result is null.