Find the Kth Smallest Element in a BST Using Go

This program uses an in-order traversal to find the kth smallest element in a Binary Search Tree (BST). The BST is traversed in increasing order and the kth element is returned.

Program Explanation

The Binary Search Tree is implemented with a struct for the tree nodes and contains integer values. The tree is traversed in-order (left-root-right) which naturally processes elements in sorted order.

Code Structure

1. TreeNode struct: Defines the structure of the BST nodes.
2. kthSmallest function: Main logic to find the kth smallest element.
3. inOrder function: Recursive helper function to perform in-order traversal and track the order of elements.

Code with Documentation

package main

import (
    "fmt"
)

// TreeNode defines a binary search tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// kthSmallest finds the kth smallest element in the BST.
func kthSmallest(root *TreeNode, k int) int {
    // Initialize a slice to capture the traversal sequence
    elements := make([]int, 0)
    inOrder(root, &elements)

    // k is 1-based index, adjust it for 0-based slice index
    return elements[k-1]
}

// inOrder performs in-order traversal of the BST.
// It appends node values to the slice elements in ascending order.
func inOrder(node *TreeNode, elements *[]int) {
    if node == nil {
        return
    }
    // Traverse left subtree
    inOrder(node.Left, elements)
    // Visit the node
    *elements = append(*elements, node.Val)
    // Traverse right subtree
    inOrder(node.Right, elements)
}

func main() {
    // Example BST: [3, 1, 4, nil, 2]
    root := &TreeNode{3, &TreeNode{1, nil, &TreeNode{2, nil, nil}}, &TreeNode{4, nil, nil}}
    // Find the 2nd smallest element
    fmt.Println("The 2nd smallest element is:", kthSmallest(root, 2))
}

Conclusion

This program efficiently finds the kth smallest element in a BST by leveraging in-order traversal, which ensures that elements are processed in their natural order. The use of a slice to track elements visited during the traversal allows easy access to the kth smallest element by indexing directly into the slice.