NUHMAN.com

🧩 Problem Statement

Given a binary search tree, write a function to find the kth smallest element in it.

A binary search tree (BST) is a tree in which for every node:

• The left subtree's node values are less than the node’s value.
• The right subtree's node values are greater than the node’s value.

You need to implement the following function:

go

func kthSmallest(root *TreeNode, k int) int

📘 Example

go

Input: root = [3,1,4,null,2], k = 1
Output: 1

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

📝 Explanation:

1. Example 1:

• The tree looks like:

markdown

    3
   / \
  1   4
   \
    2

• The in-order traversal (left, root, right) of this BST would be [1, 2, 3, 4].
• The 1st smallest element is 1.

1. Example 2:

• The tree looks like:

markdown

    5
   / \
  3   6
 / \   
2   4

1. / 1

markdown

- The in-order traversal of this BST would be `[1, 2, 3, 4, 5, 6]`.
- The **3rd** smallest element is `3`.

🧠 Approach

The most efficient way to find the kth smallest element in a Binary Search Tree (BST) is to use in-order traversal, as it produces the nodes in ascending order.

1. In-order Traversal:

• Perform a recursive traversal of the tree (left subtree, root, right subtree).
• Count the number of elements visited during the traversal.
• Once we have visited k elements, the kth element is the answer.

1. Optimization:

• We can stop the traversal as soon as we have visited k nodes, thus reducing unnecessary work.

✅ Go Implementation

go

package main

import "fmt"

// TreeNode represents a node in the binary search tree
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// In-order traversal function with a counter to find the kth smallest element
var count, result int

// Function to perform in-order traversal
func inOrderTraversal(root *TreeNode, k int) {
    if root == nil || count >= k {
        return
    }

    // Traverse the left subtree
    inOrderTraversal(root.Left, k)

    // Visit the current node
    count++
    if count == k {
        result = root.Val
        return
    }

    // Traverse the right subtree
    inOrderTraversal(root.Right, k)
}

// Function to find the kth smallest element in the BST
func kthSmallest(root *TreeNode, k int) int {
    count = 0
    result = 0
    inOrderTraversal(root, k)
    return result
}

// Helper function to create a binary search tree
func createBST(values []int) *TreeNode {
    var root *TreeNode
    for _, val := range values {
        root = insertBST(root, val)
    }
    return root
}

// Helper function to insert a value into the BST
func insertBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }
    if val < root.Val {
        root.Left = insertBST(root.Left, val)
    } else {
        root.Right = insertBST(root.Right, val)
    }
    return root
}

// Test the kthSmallest function
func main() {
    // Test case 1
    tree1 := createBST([]int{3, 1, 4, 2})
    fmt.Println(kthSmallest(tree1, 1)) // Output: 1

    // Test case 2
    tree2 := createBST([]int{5, 3, 6, 2, 4, 1})
    fmt.Println(kthSmallest(tree2, 3)) // Output: 3
}

📦 Example Usage

go

func main() {
    // Test case 1
    tree1 := createBST([]int{3, 1, 4, 2})
    fmt.Println(kthSmallest(tree1, 1)) // Output: 1

    // Test case 2
    tree2 := createBST([]int{5, 3, 6, 2, 4, 1})
    fmt.Println(kthSmallest(tree2, 3)) // Output: 3
}

⏱️ Time & Space Complexity

• Time Complexity:
• O(H + k), where H is the height of the tree and k is the number of nodes we need to visit. In the worst case, the height of the tree could be O(n), so the time complexity is O(n + k).
• O(k) is the number of nodes visited before finding the kth smallest element.
• Space Complexity:
• O(H), where H is the height of the tree. This is due to the recursion stack of the in-order traversal.

This solution efficiently finds the kth smallest element in a BST using in-order traversal. The approach stops as soon as we have found the kth smallest element, which optimizes the solution.