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

func kthSmallest(root *TreeNode, k int) int {
    count := 0
    var result int
    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil || count >= k {
            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 doing an inorder traversal and counting nodes.

Execution Table

Step	Operation	Current Node	Count	Action	Visual State
1	Start at root	5	0	Go left	5 / \ 3 7 / \ 2 4 8
2	Go left	3	0	Go left	5 / \ 3 7 / \ 2 4 8
3	Go left	2	0	Go left (nil)	5 / \ 3 7 / \ 2 4 8
4	Left nil	nil	0	Return	5 / \ 3 7 / \ 2 4 8
5	Visit node	2	1	Count=1	Visited: 2
6	Check count	2	1	count != k(3), go right	Visited: 2
7	Go right	nil	1	Return	Visited: 2
8	Return to parent	3	2	Count=2	Visited: 2 -> 3
9	Check count	3	2	count != k(3), go right	Visited: 2 -> 3
10	Go right	4	2	Go left (nil)	Visited: 2 -> 3
11	Left nil	nil	2	Return	Visited: 2 -> 3
12	Visit node	4	3	Count=3	Visited: 2 -> 3 -> 4
13	Check count	4	3	count == k(3), set result=4	Visited: 2 -> 3 -> 4
14	Stop traversal	4	3	Return	Result found: 4
15	Return result	root	3	Return 4	Final result: 4

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

Variable Tracker

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

Key Moments - 3 Insights

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

Because once count equals k (see step 13 in execution_table), we have found the kth smallest node, so continuing traversal is unnecessary and inefficient.

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

Inorder traversal visits nodes in ascending order for BSTs. Left subtree nodes are smaller, so we visit them first (see steps 2-5).

What happens if the BST has fewer than k nodes?

The traversal finishes without count reaching k, so result remains default (0 here). The code returns 0 or an invalid value indicating kth element doesn't exist.

Visual Quiz - 3 Questions

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

A 2

B 3

C 1

D 0

💡 Hint

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

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

A Step 12

B Step 14

C Step 13

D Step 15

💡 Hint

Look for the step where 'count == k' and result is set in execution_table.

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

A 2

B 3

C 4

D 5

💡 Hint

Check variable_tracker for count and result values at count=2 in execution_table.

Concept Snapshot

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

Full Transcript

To find the kth smallest element in a binary search tree, we do an inorder traversal. This means we first go as far left as possible, then visit the current node, then go right. We keep a count of how many nodes we have visited. When the count reaches k, we have found the kth smallest element and return its value. The traversal stops immediately after finding this node to save time. If the tree has fewer than k nodes, the function returns 0 or a default value. This method works because inorder traversal visits nodes in ascending order in a BST.