How do you solve Kth Smallest Element in a BST on LeetCode?

Kth Smallest Element in a BST (LeetCode #230) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: In-order traversal of a BST gives elements in sorted order.

What is the brute force solution for Kth Smallest Element in a BST?

The brute force approach for Kth Smallest Element in a BST is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute-force approach involves traversing the entire tree and collecting all the values in a list. Once we have all the values, we can sort them and find the k-th smallest element. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Kth Smallest Element in a BST?

Kth Smallest Element in a BST uses the following concepts: Tree, Depth-First Search, Binary Search Tree, Binary Tree. The recommended patterns to study are: In-order Traversal, Stack-based Iteration.

What are the interview tips for Kth Smallest Element in a BST?

Always clarify whether k is 0-indexed or 1-indexed. Discuss the properties of BSTs and how they can be leveraged. Practice writing both recursive and iterative solutions.

What are common mistakes when solving Kth Smallest Element in a BST?

Forgetting that the k is 1-indexed. Not handling edge cases like empty trees or invalid k values.

#230

Kth Smallest Element in a BST

Medium

TreeDepth-First SearchBinary Search TreeBinary TreeIn-order TraversalStack-based Iteration

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal approach utilizes the properties of a Binary Search Tree (BST) and performs an in-order traversal. This traversal visits nodes in ascending order, allowing us to find the k-th smallest element efficiently without needing to sort all values.

⚙️

Algorithm

3 steps

1Step 1: Initialize a counter to track the number of nodes visited.
2Step 2: Perform an in-order traversal of the BST.
3Step 3: When the counter equals k, return the current node's value.

solution.py20 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8def kthSmallest(root: TreeNode, k: int) -> int:
9    stack = []
10    current = root
11    count = 0
12    while True:
13        while current:
14            stack.append(current)
15            current = current.left
16        current = stack.pop()
17        count += 1
18        if count == k:
19            return current.val
20        current = current.right

ℹ

Complexity note: The time complexity is O(n) in the worst case when we traverse all nodes. The space complexity is O(h) where h is the height of the tree, due to the stack used for the in-order traversal.

1In-order traversal of a BST gives elements in sorted order.
2Using a stack can help simulate recursion and manage the traversal state.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.