#230

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Kth Smallest Element in a BST

Find the kth smallest element in a BST by leveraging in-order traversal to efficiently track node order and count.

tree depth first search binary search tree binary tree

Problem Statement

Given the root of a binary search tree and an integer k, return the kth smallest value among all node values. The tree follows standard BST properties where left children are smaller than the node and right children are larger.

You must implement an approach that efficiently finds this element without fully flattening the tree, making use of in-order traversal and careful state tracking to minimize unnecessary recursion and storage.

Examples

Example 1

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

Output: 1

Example details omitted.

Example 2

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

Output: 3

Example details omitted.

Constraints

The number of nodes in the tree is n.
1 <= k <= n <= 104
0 <= Node.val <= 104

Solution Approach

Recursive In-Order Traversal with Counter

Perform a standard in-order traversal, incrementing a counter at each node. Once the counter equals k, record the node's value and terminate recursion to avoid extra work.

Iterative In-Order Traversal using Stack

Use an explicit stack to simulate in-order traversal iteratively. Push left children, process nodes while counting, and stop when the kth element is reached, reducing call stack overhead.

Optimized BST with Node Counts

Augment the BST nodes with subtree sizes to allow O(log n) navigation. Compare k with left subtree counts to move left or right, efficiently jumping over unneeded nodes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(h + k) for recursive or iterative traversal, where h is tree height, to O(log n) per query with augmented BST. Space complexity is O(h) for recursion stack or stack in iteration, or O(1) additional if using counts in augmented nodes.

What Interviewers Usually Probe

Are you leveraging the BST property to avoid unnecessary traversal?
How do you track the count without storing all elements?
Can you optimize for repeated kth queries with minimal extra storage?

Common Pitfalls or Variants

Common pitfalls

Confusing in-order traversal order in a BST and miscounting nodes.
Using full tree flattening which increases space unnecessarily.
Failing to stop traversal after reaching the kth element, wasting time.

Follow-up variants

Find kth largest element in a BST by reversing in-order traversal.
Handle dynamic BSTs with insertions and deletions while supporting kth smallest queries.
Compute kth smallest element in a BST with duplicates allowed, considering duplicate counts.

FAQ

What is the main strategy for finding the kth smallest element in a BST?

Use in-order traversal while maintaining a counter; the kth visited node is the answer.

Can this problem be solved iteratively without recursion?

Yes, a stack can simulate in-order traversal, counting nodes until reaching k.

How does BST structure help in this problem?

BST property allows skipping entire subtrees that do not contain the kth element, reducing traversal.

What is the time complexity for this approach?

O(h + k), where h is tree height, because traversal stops once the kth element is found.

Are there variants of this problem using similar traversal patterns?

Yes, such as kth largest element, BSTs with duplicates, or dynamic BST queries.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stk = []
        while root or stk:
            if root:
                stk.append(root)
                root = root.left
            else:
                root = stk.pop()
                k -= 1
                if k == 0:
                    return root.val
                root = root.right

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stk = []
        while root or stk:
            if root:
                stk.append(root)
                root = root.left
            else:
                root = stk.pop()
                k -= 1
                if k == 0:
                    return root.val
                root = root.right

Continue Practicing

#235 lowest common ancestor of a binary search tree #99 recover binary search tree #98 validate binary search tree