Kth Smallest Element in BST in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Function

What is the output of the following Go code that finds the 3rd smallest element in a BST?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    current := root
    count := 0
    for current != nil || len(stack) > 0 {
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        count++
        if count == k {
            return current.Val
        }
        current = current.Right
    }
    return -1
}

func main() {
    root := &TreeNode{Val: 5}
    root.Left = &TreeNode{Val: 3}
    root.Right = &TreeNode{Val: 6}
    root.Left.Left = &TreeNode{Val: 2}
    root.Left.Right = &TreeNode{Val: 4}
    root.Left.Left.Left = &TreeNode{Val: 1}
    fmt.Println(kthSmallest(root, 3))
}

A 4

B 2

C 3

D 5

💡 Hint

Remember that an in-order traversal of a BST visits nodes in ascending order.

The in-order traversal visits nodes in this order: 1, 2, 3, 4, 5, 6. The 3rd smallest element is 3.

🧠 Conceptual

intermediate

Understanding Kth Smallest Element in BST

Which property of a Binary Search Tree (BST) allows the kth smallest element to be found efficiently using in-order traversal?

A In-order traversal of BST visits nodes in ascending order

B BST nodes are stored in a sorted linked list

C BST nodes have pointers to their parents

D BST is always a balanced tree

💡 Hint

Think about the order in which nodes are visited during in-order traversal.

In-order traversal of a BST visits nodes in ascending order of their values, which allows us to find the kth smallest element by counting nodes visited.

🔧 Debug

advanced

Identify the Error in Kth Smallest Element Code

What error will the following Go code produce when trying to find the 2nd smallest element in a BST?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func kthSmallest(root *TreeNode, k int) int {
    var count int
    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
}

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 2}
    fmt.Println(kthSmallest(root, 2))
}

A The code returns 2 correctly

B The code returns 1 instead of 2

C The code causes a stack overflow

D The code returns 0 instead of 2

💡 Hint

Check if the recursion stops after finding the kth element.

The recursion does not stop after finding the kth element because the return inside the inner function only exits that call, not the entire traversal. So result is set but traversal continues, and result may be overwritten or default zero returned.

❓ Predict Output

advanced

Output of Modified Kth Smallest Element Code

What is the output of this Go code that finds the 4th smallest element in a BST with duplicate values?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    current := root
    count := 0
    for current != nil || len(stack) > 0 {
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        count++
        if count == k {
            return current.Val
        }
        current = current.Right
    }
    return -1
}

func main() {
    root := &TreeNode{Val: 5}
    root.Left = &TreeNode{Val: 3}
    root.Right = &TreeNode{Val: 6}
    root.Left.Left = &TreeNode{Val: 3}
    root.Left.Right = &TreeNode{Val: 4}
    fmt.Println(kthSmallest(root, 4))
}

A 3

B 4

C 5

D -1

💡 Hint

Duplicates appear in in-order traversal as repeated values.

The in-order traversal visits nodes in order: 3, 3, 4, 5, 6. The 4th smallest element is 4.

🚀 Application

expert

Optimizing Kth Smallest Element Search with Augmented BST

You want to find the kth smallest element in a BST efficiently multiple times. Which data structure modification helps achieve O(log n) time per query?

A Store subtree sizes at each node to guide search

B Convert BST to a sorted array and binary search

C Use a hash map to store node values and their ranks

D Perform full in-order traversal each time to find kth element

💡 Hint

Think about augmenting nodes with extra info to skip parts of the tree.

Storing subtree sizes at each node allows deciding whether to go left, right, or return current node based on k, achieving O(log n) time per query.