Skip to main content
Talentd

Kth Smallest Element in a BST - Solution & Explanation

MediumTreeDepth-First SearchBinary Search TreeBinary Tree16 min readAsked at: Amazon, Microsoft, Meta +9
Practice this problem

Problem Statement

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

 

Example 1:

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

Example 2:

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

 

Constraints:

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

 

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Approach Overview

Problem Overview: Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest value among all nodes. The key observation is that an in-order traversal of a BST visits nodes in strictly increasing order.

The BST property makes this problem straightforward once you recognize the traversal order. In-order traversal processes nodes as left → root → right, which naturally produces a sorted sequence. Instead of storing the entire sequence, you only need to count nodes until the kth element appears.

Approach 1: In-Order Traversal (Recursive) (O(n) time, O(h) space)

This approach performs a standard in-order traversal of the tree. Maintain a counter that increments every time you visit a node. Once the counter equals k, return that node’s value immediately. Because a BST guarantees sorted order during in-order traversal, the kth visited node is the kth smallest element.

The recursion stack holds at most h nodes where h is the tree height. In a balanced tree this is O(log n), but in the worst case (skewed tree) it becomes O(n). This solution is simple, easy to reason about, and commonly expected in interviews involving tree traversal or depth-first search.

Approach 2: Morris In-Order Traversal (Iterative) (O(n) time, O(1) space)

Morris Traversal performs in-order traversal without recursion or an explicit stack. It temporarily modifies the tree by creating threaded links from a node’s predecessor back to the current node. This allows traversal to return to parent nodes without storing them in memory.

During traversal, increment a counter each time a node is processed. When the counter reaches k, return the current value. After visiting a node, restore the modified pointers so the tree structure remains unchanged. This method achieves constant extra space while still visiting each node at most twice.

Morris traversal is especially useful when memory usage must stay minimal. It’s less commonly written in interviews but demonstrates strong understanding of binary search tree traversal mechanics.

Recommended for interviews: The recursive in-order traversal is the expected answer in most interviews because it directly uses the BST ordering property and is easy to implement quickly. Mentioning Morris traversal as a follow-up shows deeper knowledge of tree traversal optimizations and space reduction techniques.

Approach 1: In-Order Traversal (Recursive)

In a Binary Search Tree (BST), an in-order traversal visits nodes in ascending order. To find the kth smallest element, perform an in-order traversal and count the nodes until you reach the kth one.

This solution uses a recursive in-order traversal to find the kth smallest element. We decrement k each time we visit a node and check if it reaches 0, signifying the kth element. If it does, we record the current node's value and exit further recursion.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(n) (due to recursion stack in worst case).

Try this approach in the editor →

Approach 2: Morris In-Order Traversal (Iterative)

Morris Traversal is a way to perform in-order traversal with O(1) extra space. This method modifies the tree's structure temporarily to avoid the recursive call stack. This approach uses the concept of threading where leaf nodes point to their in-order successor to facilitate traversal.

This C implementation uses the Morris Traversal to avoid recursion. The traversal temporarily alters the tree's structure to keep track of each node's predecessor, thereby facilitating efficient space management.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
In-Order Traversal (Recursive)

Time Complexity: O(n), Space Complexity: O(n) (due to recursion stack in worst case).

Morris In-Order Traversal (Iterative)

Time Complexity: O(n), Space Complexity: O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
In-Order Traversal (Recursive)O(n)O(h)General interview solution; simple and leverages BST ordering
Morris In-Order TraversalO(n)O(1)When minimizing extra memory or demonstrating advanced traversal techniques

Video Solution

Kth Smallest Element in a BST - Leetcode 230 - Python • NeetCode • 266,719 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Kth Smallest Element in a BST easy or hard?
The problem is rated Medium because recognizing the in-order traversal property of BSTs is the key insight. Once that observation is made, the implementation is straightforward, but interviewers may ask follow-ups such as reducing space to O(1) using Morris traversal.
Kth Smallest Element in a BST Python/Java solution
Python and Java implementations typically use recursive in-order traversal with a global or reference counter. Each node visit increments the counter until the kth node is found. The same logic works in C++, JavaScript, and other languages because it depends only on tree traversal order.
How to solve Kth Smallest Element in a BST in O(n)?
Perform an in-order traversal of the BST and maintain a counter for visited nodes. Increment the counter each time a node is processed. When the counter equals k, return that node’s value. This guarantees O(n) time because each node is visited at most once.
What is the best approach for Kth Smallest Element in a BST?
In-order traversal is the best approach because a Binary Search Tree outputs nodes in sorted order when traversed left → root → right. Counting nodes during traversal allows you to stop once the kth node is reached. This method runs in O(n) time and O(h) space where h is the tree height.
Is Kth Smallest Element in a BST asked at Google/Amazon/Meta?
Kth Smallest Element in a BST appears frequently in interviews at companies like Amazon, Google, and Meta. It tests understanding of BST ordering, depth-first traversal, and the ability to optimize space using techniques such as Morris traversal.
What data structure is used in Kth Smallest Element in a BST?
The core data structure is a Binary Search Tree. Solutions rely on depth-first traversal, usually in-order traversal, and may use recursion stacks or pointer threading (Morris traversal) to navigate the tree efficiently.
What is the time complexity of Kth Smallest Element in a BST?
Most solutions run in O(n) time because in the worst case you may need to visit every node. Recursive in-order traversal uses O(h) space for the recursion stack, while Morris traversal reduces extra space to O(1) by temporarily modifying tree pointers.

Ready to solve this problem?

Practice Kth Smallest Element in a BST with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Second Minimum Node In a Binary Tree