LeetCode 230: Kth Smallest Element in a BST Solution in Python – A Step-by-Step Guide
Picture navigating a binary search tree to pinpoint the kth smallest element—that’s the challenge of LeetCode 230: Kth Smallest Element in a BST! This medium-level problem asks you to find the kth smallest value in a binary search tree (BST), leveraging its ordered structure. Using Python, we’ll explore two solutions: the Best Solution (inorder traversal with a counter) for its space efficiency, and an Alternative Solution (inorder traversal with array storage) for its simplicity. With beginner-friendly breakdowns, detailed examples, and clear code, this guide will help you master BST traversal and sharpen your coding skills. Let’s find that kth element!
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:
```
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:
# 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
class 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!