LogoKode$word

LeetCode 230: Kth Smallest Element in a BST – Java Recursive Inorder Traversal Solution

Learn how to solve LeetCode 230 Kth Smallest Element in a BST using inorder traversal in Java. Includes BST intuition, brute force approach, optimized recursive solution, dry run, complexity analysis, interview explanation, and common mistakes.

Krishna Shrivastava
0 views
LinkedInGithubX
0
0
LeetCodeKth Smallest Element in BSTBinary Search TreeJavaInorder TraversalBSTMedium
LeetCode 230: Kth Smallest Element in a BST – Java Recursive Inorder Traversal Solution
Listen to articleAudio version
Ad
Advertisement

Introduction

LeetCode 230 – Kth Smallest Element in a BST is one of the most important Binary Search Tree interview problems.

This question is popular because it tests:

  1. BST properties
  2. Inorder traversal
  3. DFS recursion
  4. Tree traversal optimization
  5. Recursive state management

Understanding this problem properly builds a strong foundation for advanced BST problems.

Problem Link

🔗 https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Problem Statement

Given:

  1. Root of a Binary Search Tree
  2. Integer k

Return:

The kth smallest value in the BST

The indexing is:

1-indexed

Example 1

Input

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

Output

1

Explanation

BST inorder traversal becomes:

[1,2,3,4]

1st smallest element is:

1

Example 2

Input

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

Output

3

Key Observation

The most important BST property:

Inorder Traversal of BST gives sorted order

Example:

5
/ \
3 6
/ \
2 4
/
1

Inorder traversal:

1 → 2 → 3 → 4 → 5 → 6

So:

kth smallest = kth node in inorder traversal

Intuition

We perform:

Left → Root → Right

While traversing:

  1. Keep counting visited nodes
  2. When count becomes k
  3. Store answer

No need to traverse entire tree after finding answer.

Brute Force Approach

Idea

  1. Store complete inorder traversal in list
  2. Return:
list.get(k - 1)

Brute Force Java Solution

class Solution {

public void inorder(TreeNode root, List<Integer> list) {

if(root == null) return;

inorder(root.left, list);

list.add(root.val);

inorder(root.right, list);
}

public int kthSmallest(TreeNode root, int k) {

List<Integer> list = new ArrayList<>();

inorder(root, list);

return list.get(k - 1);
}
}

Complexity of Brute Force

Time Complexity

O(N)

Space Complexity

O(N)

Extra list storage required.

Optimized Recursive Approach

Idea

Instead of storing entire traversal:

  1. Maintain counter
  2. Stop when kth node is reached

This saves unnecessary storage.

Java Solution

class Solution {

int coun = 0;
int ans = -1;

public void inorder(TreeNode root, int k, List<Integer> lis) {

if(root == null) return;

inorder(root.left, k, lis);

coun++;

if(coun == k) {
ans = root.val;
return;
}

inorder(root.right, k, lis);
}

public int kthSmallest(TreeNode root, int k) {

List<Integer> lis = new ArrayList<>();

inorder(root, k, lis);

return ans;
}
}

Cleaner Optimized Version

class Solution {

int count = 0;
int answer = -1;

public void inorder(TreeNode root, int k) {

if(root == null) return;

inorder(root.left, k);

count++;

if(count == k) {
answer = root.val;
return;
}

inorder(root.right, k);
}

public int kthSmallest(TreeNode root, int k) {

inorder(root, k);

return answer;
}
}

Why This Works

BST inorder traversal always visits nodes in:

sorted ascending order

So:

  1. 1st visited node = smallest
  2. 2nd visited node = second smallest
  3. kth visited node = kth smallest

Dry Run

Input

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

BST Structure

5
/ \
3 6
/ \
2 4
/
1

Inorder Traversal

1 → 2 → 3 → 4 → 5 → 6

Counter Progress

NodeCount
11
22
33

At count = 3:

answer = 3

Final Output

3

Iterative Stack Approach

Idea

Use explicit stack instead of recursion.

Iterative Java Solution

class Solution {

public int kthSmallest(TreeNode root, int k) {

Stack<TreeNode> stack = new Stack<>();

while(true) {

while(root != null) {
stack.push(root);
root = root.left;
}

root = stack.pop();

k--;

if(k == 0) {
return root.val;
}

root = root.right;
}
}
}

Time Complexity Analysis

Optimized Recursive

Time Complexity

O(H + k)

Where:

  1. H = tree height
  2. We visit only required nodes

Worst case:

O(N)

Space Complexity

O(H)

Recursive stack space.

Iterative Complexity

Time Complexity

O(H + k)

Space Complexity

O(H)

Stack space.

Follow-Up Optimization

Problem Follow-Up

What if BST changes frequently?

Example:

  1. Insert operations
  2. Delete operations
  3. Frequent kth smallest queries

Advanced Optimization

Store:

size of subtree

inside every node.

This allows:

O(log N)

kth smallest queries.

This concept is used in:

  1. Order Statistic Trees
  2. Augmented BSTs
  3. Indexed Trees

Interview Explanation

In interviews, explain:

Inorder traversal of a BST gives nodes in sorted order. Therefore, the kth visited node during inorder traversal is the kth smallest element.

This demonstrates:

  1. BST understanding
  2. DFS recursion
  3. Tree traversal mastery
  4. Optimization thinking

Common Mistakes

1. Forgetting BST Property

This solution works because BST inorder traversal is sorted.

Not true for normal binary trees.

2. Using Extra Array Unnecessarily

Optimized approach avoids storing entire traversal.

3. Incorrect Counter Placement

Counter must increase:

AFTER left traversal
BEFORE right traversal

4. Forgetting Early Return

Once kth element is found:

answer should be stored immediately

FAQs

Q1. Why does inorder traversal work?

Because BST inorder traversal produces sorted order.

Q2. Can this be solved iteratively?

Yes.

Using stack-based inorder traversal.

Q3. Why is BST important here?

Without BST ordering property:

kth smallest cannot be determined using inorder

Q4. Is this frequently asked?

Yes.

It is one of the most common BST interview questions.

Conclusion

LeetCode 230 is an excellent BST problem for mastering:

  1. Inorder traversal
  2. BST properties
  3. DFS recursion
  4. Stack traversal
  5. Tree optimization

The core insight is:

Inorder traversal of a BST always produces sorted order.

Once this concept becomes intuitive, many BST interview problems become much easier.

Related Articles

LeetCode 144: Binary Tree Preorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 144: Binary Tree Preorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 144 Binary Tree Preorder Traversal using Recursive and Iterative approaches in Java. Includes traversal intuition, stack-based solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 94 Binary Tree Inorder Traversal using Recursive and Iterative approaches in Java. Includes tree traversal intuition, dry run, stack-based solution, complexity analysis, interview tips, and common mistakes.

Read Article
LeetCode 145: Binary Tree Postorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 145: Binary Tree Postorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 145 Binary Tree Postorder Traversal using Recursive and Iterative approaches in Java. Includes traversal intuition, stack-based solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
Search in a Binary Search Tree (LeetCode 700) Java Solution with Explanation and Dry Run

Search in a Binary Search Tree (LeetCode 700) Java Solution with Explanation and Dry Run

Learn how to efficiently search for a value in a Binary Search Tree using Java with step-by-step explanation, intuition, recursion approach, dry run, and complexity analysis.

Read Article
Ai Assistant Kas