LeetCode 230: Kth Smallest Element in a BST Solution in Python – A Step-by-Step Guide

What Is LeetCode 230: Kth Smallest Element in a BST?

In LeetCode 230: Kth Smallest Element in a BST, you’re given the root of a binary search tree and an integer k, and your task is to return the kth smallest element (1-indexed). A BST’s property—left subtree values are less than the node, and right subtree values are greater—makes this a perfect fit for inorder traversal. This differs from array-based problems like LeetCode 229: Majority Element II, focusing instead on tree navigation.

Problem Statement

• Input: Root of a BST and an integer k.
• Output: The kth smallest element in the BST.
• Rules: Use BST properties to locate the kth value in sorted order.

Constraints

• Number of nodes: 1 to 10^4.
• Node values: -2^31 to 2^31 - 1.
• k: 1 to number of nodes.

Examples

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

Copy code```
  3
 / \
1   4
 \
  2
```

• Output: 1 (smallest element).

• Tree:

5 / \ 3 6 / \ 2 4 / 1

• Output: 3 (3rd smallest: 1,2,3).

Understanding the Problem: Finding the Kth Smallest

To solve LeetCode 230: Kth Smallest Element in a BST in Python, we use the BST’s inorder traversal (left-root-right), which visits nodes in ascending order. This isn’t about inverting trees like LeetCode 226: Invert Binary Tree—it’s about ordered traversal. We’ll explore two approaches: 1. Best Solution (Inorder with Counter): O(h + k) time, O(h) space—stops early, saves space. 2. Alternative Solution (Inorder with Array): O(n) time, O(n) space—stores all values.

Let’s start with the best solution.

Best Solution: Inorder Traversal with Counter

Why This Is the Best Solution

The inorder traversal with a counter is our top choice for LeetCode 230 because it processes nodes in order, stops once the kth element is found, and uses minimal extra space. It’s efficient and leverages the BST’s structure beautifully, making it ideal for this task.

How It Works

• Traverse the tree inorder (left-root-right).
• Use a counter to track the number of nodes visited.
• When the counter hits k, return the current node’s value.
• Optimize by tracking state globally or via a class variable.

Step-by-Step Example

Example 1: [3,1,4,null,2], k = 1

• Tree:

3 / \ 1 4 \ 2

• Inorder: 1,2,3,4.
• Counter = 0.
• Visit 1: Counter = 1, k = 1, return 1.

Example 2: [5,3,6,2,4,null,null,1], k = 3

• Tree:

5 / \ 3 6 / \ 2 4 / 1

• Inorder: 1,2,3,4,5,6.
• Counter = 0.
• 1: Counter = 1.
• 2: Counter = 2.
• 3: Counter = 3, k = 3, return 3.

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

Copy code# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        self.count = 0  # Track nodes visited
        self.result = 0  # Store kth value

    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def inorder(node):
            # Line 1: Base case - empty node
            if not node:
                return

            # Line 2: Process left subtree
            inorder(node.left)

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

            # Line 4: Process right subtree
            inorder(node.right)

        # Line 5: Start traversal
        inorder(root)

        # Line 6: Return kth smallest
        return self.result

• Time Complexity: O(h + k) – traverses height h to leftmost, then k nodes.
• Space Complexity: O(h) – stack depth for BST height.

Alternative Solution: Inorder Traversal with Array Storage

Why an Alternative Approach?

The inorder traversal with array storage collects all values in sorted order, then picks the kth element. It’s a great alternative if you prefer simplicity or need all elements for further processing, though it uses more space.

How It Works

• Traverse the BST inorder, storing values in an array.
• Return the kth element (k-1 index, since 1-indexed).

Step-by-Step Example

Example: [5,3,6,2,4,null,null,1], k = 3

• Inorder: Store [1,2,3,4,5,6].
• k = 3, index = 2 (0-based), return 3.

Code for Array Storage Approach

Copy codeclass Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        # Line 1: Initialize array for values
        values = []

        def inorder(node):
            # Line 2: Base case
            if not node:
                return

            # Line 3: Left subtree
            inorder(node.left)
            # Line 4: Current node
            values.append(node.val)
            # Line 5: Right subtree
            inorder(node.right)

        # Line 6: Perform traversal
        inorder(root)

        # Line 7: Return kth element
        return values[k-1]

• Time Complexity: O(n) – traverses all nodes.
• Space Complexity: O(n) – stores all values.

Comparing the Two Solutions

• Best Solution (Inorder with Counter):
• Pros: Stops at k, O(h + k) time, O(h) space.
• Cons: Slightly more complex state management.
• Alternative Solution (Inorder with Array):
• Pros: Simple, straightforward.
• Cons: O(n) time and space, overkill for large trees.

The counter-based method is our best for efficiency and space.

Additional Examples and Edge Cases

Single Node

• Input: [1], k = 1
• Output: 1
• Both return 1.

Full BST

• Input: [4,2,6,1,3,5,7], k = 4
• Inorder: [1,2,3,4,5,6,7], output: 4.
• Both work correctly.

Left-Skewed

• Input: [3,2,null,1], k = 2
• Inorder: [1,2,3], output: 2.
• Both handle seamlessly.

Complexity Breakdown

• Inorder with Counter:
• Time: O(h + k).
• Space: O(h).
• Inorder with Array:
• Time: O(n).
• Space: O(n).

Counter method optimizes time and space.

Key Takeaways for Beginners

• BST Property: Inorder gives sorted order.
• Counter: Tracks position efficiently.
• Array: Stores all values simply.
• Python Tip: Class variables track state—see [Python Basics](/python/basics).

Final Thoughts: Find the Kth Smallest Like a Pro

LeetCode 230: Kth Smallest Element in a BST in Python is a fantastic way to master BST traversal. The inorder with counter solution offers efficiency and elegance, while the array storage approach keeps it simple. Want more tree challenges? Try LeetCode 104: Maximum Depth of Binary Tree or LeetCode 98: Validate Binary Search Tree. Ready to traverse? Head to Solve LeetCode 230 on LeetCode and find that kth element today!