Skip to main content

🟨 Kth Smallest Element in a BST (#230)

🔗 Problem Link​

📋 Problem Statement​

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

💡 Examples​

Example 1​

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

Example 2​

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

🔑 Key Insights & Approach​

Core Observation: Inorder traversal of BST produces sorted values. Stop at kth element.

Why Inorder Traversal?

  • O(h + k) time in best case
  • O(h) space for recursion
  • Leverages BST property

Approaches:

  1. Inorder traversal with counter: O(h + k) time, O(h) space - optimal
  2. Build sorted array then index: O(n) time, O(n) space
  3. Iterative inorder with stack: O(h + k) time, O(h) space

Pattern: "BST Inorder Traversal" for kth element problems.

🐍 Solution: Python​

Approach 1: Recursive Inorder with Counter​

Time Complexity: O(h + k) | Space Complexity: O(h)

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.count = 0
        self.result = None

        def inorder(node):
            if not node or self.result is not None:
                return

            # Traverse left
            inorder(node.left)

            # Process current node
            self.count += 1
            if self.count == k:
                self.result = node.val
                return

            # Traverse right
            inorder(node.right)

        inorder(root)
        return self.result

Approach 2: Iterative with Stack​

Time Complexity: O(h + k) | Space Complexity: O(h)

from typing import Optional

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        current = root
        count = 0

        while current or stack:
            # Go to leftmost node
            while current:
                stack.append(current)
                current = current.left

            # Process node
            current = stack.pop()
            count += 1

            if count == k:
                return current.val

            # Go to right subtree
            current = current.right

        return -1

🔵 Solution: Golang​

Approach: Iterative Inorder​

Time Complexity: O(h + k) | Space Complexity: O(h)

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 {
        // Go to leftmost
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }

        // Process node
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        count++

        if count == k {
            return current.Val
        }

        current = current.Right
    }

    return -1
}

📚 References​