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.

Practice

1. What does the term Kth Smallest Element in BST mean?

easy

A. The element with the highest frequency in the BST

B. The element at the root of the BST

C. The largest element in the BST

D. The element that is the Kth smallest when BST elements are sorted in ascending order

Solution

1. Step 1: Understand BST property

   A Binary Search Tree (BST) stores elements so that left child nodes are smaller and right child nodes are larger than the parent node.

2. Step 2: Define Kth smallest element

   The Kth smallest element is the element that appears in the Kth position when all elements are sorted in ascending order.

3. Final Answer:

   The element that is the Kth smallest when BST elements are sorted in ascending order -> Option D

4. Quick Check:

   Kth smallest = Kth element in sorted order [OK]

Hint: Think in sorted order of BST elements [OK]

Common Mistakes:

• Confusing Kth smallest with root element
• Thinking it means largest element
• Mixing frequency with order

2. Which of the following Go function signatures correctly represents a function to find the Kth smallest element in a BST node structure named TreeNode?

easy

A. func kthSmallest(root *TreeNode) int

B. func kthSmallest(root *TreeNode, k int) int

C. func kthSmallest(root TreeNode, k int) *int

D. func kthSmallest(k int, root *TreeNode) int

Solution

1. Step 1: Check parameter order and types

   The function should take the root pointer of type *TreeNode and an integer k to specify the Kth element.

2. Step 2: Check return type

   The function returns an int representing the value of the Kth smallest element.

3. Final Answer:

   func kthSmallest(root *TreeNode, k int) int -> Option B

4. Quick Check:

   Correct parameters and return type [OK]

Hint: Root pointer first, then k, return int [OK]

Common Mistakes:

• Swapping parameter order
• Passing root by value instead of pointer
• Missing k parameter
• Wrong return type

3. Given the BST below and k = 3, what will the output of kthSmallest(root, 3) be?

      5
     / \
    3   7
   / \   \
  2   4   8

medium

A. 4

B. 5

C. 3

D. 7

Solution

1. Step 1: Perform in-order traversal

   In-order traversal visits nodes in ascending order: 2, 3, 4, 5, 7, 8.

2. Step 2: Identify the 3rd element

   The 3rd element in this order is 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   In-order 3rd element = 4 [OK]

Hint: In-order traversal gives sorted order [OK]

Common Mistakes:

• Counting root as first without traversal
• Confusing pre-order or post-order with in-order
• Off-by-one counting errors

4. Consider this Go function snippet to find the Kth smallest element in a 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 {
            return
        }
        inorder(node.Left)
        count++
        if count == k {
            result = node.Val
            return
        }
        inorder(node.Right)
    }
    inorder(root)
    return result
}

What is the main bug in this code?

medium

A. The function does not stop traversal after finding the Kth element

B. The count variable is not incremented correctly

C. The result variable is not returned

D. The inorder function is not called

Solution

1. Step 1: Analyze traversal stopping condition

   The code sets result when count == k but does not stop further recursion, so it continues traversing unnecessarily.

2. Step 2: Identify missing early return

   After finding the Kth element, the function should stop traversing to avoid overwriting result or extra work.

3. Final Answer:

   The function does not stop traversal after finding the Kth element -> Option A

4. Quick Check:

   Traversal continues after Kth found [OK]

Hint: Stop traversal immediately after finding Kth element [OK]

Common Mistakes:

• Not stopping recursion after finding result
• Incorrect count increment placement
• Returning wrong variable

5. You want to find the Kth smallest element in a BST but the tree is very large and you want to optimize the search. Which approach below best improves efficiency?

hard

A. Convert the BST to a sorted array and then pick the Kth element

B. Perform a full in-order traversal every time to find the Kth element

C. Store the count of nodes in each subtree and use it to skip branches

D. Use breadth-first search to find the Kth smallest element

Solution

1. Step 1: Understand subtree counts

   By storing the number of nodes in each subtree, we can decide if the Kth smallest is in left subtree, current node, or right subtree without full traversal.

2. Step 2: Use counts to skip branches

   If left subtree has more than or equal to k nodes, recurse left; else adjust k and recurse right, reducing unnecessary visits.

3. Final Answer:

   Store the count of nodes in each subtree and use it to skip branches -> Option C

4. Quick Check:

   Subtree counts optimize search [OK]

Hint: Use subtree node counts to jump branches [OK]

Common Mistakes:

• Doing full traversal every time
• Converting to array wastes space/time
• Using BFS which is not sorted order