Kth Smallest Element in BST in DSA Go

Mental Model

A binary search tree keeps smaller values on the left and bigger on the right. To find the kth smallest, we visit nodes in order from smallest to largest.

Analogy: Imagine a bookshelf sorted by book size from left to right. To find the kth smallest book, you start from the left and count books until you reach k.

       5
      / \
     3   7
    / \   \
   2   4   8
  /
 1

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8 -> 1, find 3rd smallest element

Goal: Find the 3rd smallest value in the BST by visiting nodes in ascending order

Step 1: Start in-order traversal at root (5), go left to 3

Current path: 5 -> [3] -> 7 -> ...

Why: Left subtree has smaller values, so start there

Step 2: Go left from 3 to 2

Current path: 5 -> 3 -> [2] -> 4 -> 7 -> ...

Why: Keep going left to find smallest values

Step 3: Go left from 2 to 1

Current path: 5 -> 3 -> 2 -> [1] -> 4 -> 7 -> ...

Why: 1 is the smallest node, visit it first

Step 4: Visit node 1 (count=1), backtrack to 2

Visited: 1 (count=1), next node: 2

Why: Count nodes visited in ascending order

Step 5: Visit node 2 (count=2), go right (no right child)

Visited: 1 -> 2 (count=2), next node: 3

Why: After left subtree, visit parent node

Step 6: Visit node 3 (count=3), stop traversal

Visited: 1 -> 2 -> 3 (count=3), found kth smallest

Why: Reached kth smallest node, return value

Result:

1 -> 2 -> [3] -> 4 -> 5 -> 7 -> 8
Answer: 3

Annotated Code

DSA Go

package main

import "fmt"

// TreeNode defines a node in BST
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// kthSmallest finds the kth smallest element in BST
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) // go left to smaller values
        if count < k {
            count++ // count visited nodes
            if count == k {
                result = node.Val // found kth smallest
                return
            }
        }
        inorder(node.Right) // go right to larger values
    }

    inorder(root)
    return result
}

func main() {
    // Construct BST
    root := &TreeNode{Val: 5}
    root.Left = &TreeNode{Val: 3}
    root.Right = &TreeNode{Val: 7}
    root.Left.Left = &TreeNode{Val: 2}
    root.Left.Right = &TreeNode{Val: 4}
    root.Right.Right = &TreeNode{Val: 8}
    root.Left.Left.Left = &TreeNode{Val: 1}

    k := 3
    fmt.Printf("%dth smallest element is %d\n", k, kthSmallest(root, k))
}

if node == nil || count >= k { return }

stop traversal if node is nil or kth element found

inorder(node.Left)

traverse left subtree to visit smaller values first

count++

increment count when visiting a node in order

if count == k { result = node.Val; return }

record kth smallest value and stop traversal

inorder(node.Right)

traverse right subtree to visit larger values

Output

3th smallest element is 3

Complexity Analysis

Time: O(h + k) because we traverse down the tree height h and visit k nodes in order

Space: O(h) due to recursion stack for tree height h

vs Alternative: Naive approach sorts all nodes O(n log n), this uses BST property to stop early at kth node

Edge Cases

k is 1 (smallest element)

Returns the smallest node value correctly

DSA Go

if count == k { result = node.Val; return }

k equals number of nodes (largest element)

Returns the largest node value after full traversal

DSA Go

if count == k { result = node.Val; return }

k is larger than number of nodes

Returns zero (default int) since kth element not found

DSA Go

if node == nil || count >= k { return }

When to Use This Pattern

When you need the kth smallest or largest element in a BST, use in-order traversal because it visits nodes in sorted order.

Common Mistakes

Mistake: Not stopping traversal after finding kth element, causing unnecessary work
Fix: Add condition to stop recursion once kth element is found

Mistake: Visiting nodes in wrong order (e.g., pre-order or post-order) which breaks sorted order
Fix: Use in-order traversal to visit nodes from smallest to largest

Summary

Finds the kth smallest value in a binary search tree by in-order traversal.

Use when you want the kth smallest element without sorting all nodes.

In-order traversal visits nodes in ascending order, so counting nodes visited gives the kth smallest.