Kth Smallest Element in a BST

Kth Smallest Element in a BST is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Inorder Traversal subpattern.

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?

Topics and companies

Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree.

Reported in interviews at Amazon, Facebook, Adobe, Microsoft, Oracle.

How to practise Kth Smallest Element in a BST on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(max(h, k)) time and O(min(h, k)) space.

Open Kth Smallest Element in a BST in the code editor, or read the Kth Smallest Element in a BST editorial for a worked solution with its approach and complexity analysis.

Where Kth Smallest Element in a BST sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Recursive Inorder Traversal subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Kth Smallest Element in a BST

Other problems that use the same Recursive Inorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

• Binary Search Tree Iterator — Medium, same subpattern
• Binary Tree Inorder Traversal — Easy, same subpattern
• Find Mode in Binary Search Tree — Easy, same subpattern
• Minimum Absolute Difference in BST — Easy, same subpattern
• Validate Binary Search Tree — Medium, same subpattern
• All Nodes Distance K in Binary Tree — Medium, same pattern