Kth Smallest Element in BST in DSA Go - Build from Scratch

Kth Smallest Element in BST

📖 Scenario: You are working with a simple phone book application that stores contacts in a Binary Search Tree (BST). Each contact has a unique number. You want to find the contact with the kth smallest number to quickly access it.

🎯 Goal: Build a Go program that creates a BST with given numbers, sets a value for k, finds the kth smallest number in the BST, and prints it.

📋 What You'll Learn

Create a BST node struct with integer values

Insert given numbers into the BST

Set an integer variable k for the kth smallest element

Write a function to find the kth smallest element in the BST using in-order traversal

Print the kth smallest element

💡 Why This Matters

🌍 Real World

Finding the kth smallest element is useful in databases and search engines to quickly access ranked data.

💼 Career

Understanding BSTs and traversal algorithms is important for software engineers working on data storage, retrieval, and optimization.

1

Create BST Node and Insert Numbers

Create a struct called Node with an integer Val and pointers Left and Right. Then create a function insert that takes a *Node and an integer val and inserts val into the BST. Finally, create a BST by inserting these numbers in order: 5, 3, 7, 2, 4, 6, 8. Store the root in a variable called root.

DSA Go

// Define Node struct and insert function
// Insert numbers 5, 3, 7, 2, 4, 6, 8 into BST and assign to root
// Your code here

Hint

Remember, in a BST, smaller values go to the left child, larger to the right.

2

Set k Value

Create an integer variable called k and set it to 3. This means you want to find the 3rd smallest number in the BST.

DSA Go

package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{Val: val}
    }
    if val < root.Val {
        root.Left = insert(root.Left, val)
    } else {
        root.Right = insert(root.Right, val)
    }
    return root
}

func main() {
    root := insert(nil, 5)
    root = insert(root, 3)
    root = insert(root, 7)
    root = insert(root, 2)
    root = insert(root, 4)
    root = insert(root, 6)
    root = insert(root, 8)

    // Set k to 3
    // Your code here
}

Hint

Just create a variable named k and assign it the value 3.

3

Write Function to Find kth Smallest Element

Write a function called kthSmallest that takes root *Node and k int and returns the kth smallest integer in the BST. Use in-order traversal to visit nodes in ascending order. Use a helper function with a counter to find the kth element.

DSA Go

package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{Val: val}
    }
    if val < root.Val {
        root.Left = insert(root.Left, val)
    } else {
        root.Right = insert(root.Right, val)
    }
    return root
}

// Write kthSmallest function here
// Your code here

func main() {
    root := insert(nil, 5)
    root = insert(root, 3)
    root = insert(root, 7)
    root = insert(root, 2)
    root = insert(root, 4)
    root = insert(root, 6)
    root = insert(root, 8)

    k := 3
}

Hint

Use in-order traversal: left child, node, right child. Keep a count and stop when count equals k.

4

Print the kth Smallest Element

In the main function, call kthSmallest(root, k) and print the returned value using fmt.Println.

DSA Go

Hint

Call fmt.Println(kthSmallest(root, k)) to print the result.