Kth Smallest Element in a BST
Updated
Problem statement
A binary search tree is given by its root, along with an integer k. Find the value that would be in place k if you listed all the values in the tree from smallest to largest.
In this tree:
- each node's value is larger than every value in its left subtree and smaller than every value in its right subtree, and
- no two nodes share a value.
Places count from 1, so k = 1 means the smallest value, and k equal to the number of nodes means the largest.
Follow-up from the interview: could the work be split across several threads? The judge does not test this; the editorial discusses it.
Function
kthSmallest(root: TreeNode, k: int) → intExamples
Example 1
root = [5,3,7,2,4,null,8]k = 4return = 5In order from smallest to largest, the values are 2, 3, 4, 5, 7, 8. The 4th one is 5, the root.
Example 2
root = [10,null,20,15,30]k = 2return = 15Node 10 has no left child. Its right child is 20, whose children are 15 and 30. In order the values are 10, 15, 20, 30, so the 2nd smallest is 15.
Example 3
root = [-3,-7,0,-9]k = 1return = -9The smallest value is the leftmost node: start at -3, go left to -7, then left to -9, which has no left child. So the answer is -9.
Constraints
- The number of nodes is between
1and10^4. -10^4 <= node.val <= 10^4- No two nodes have the same value, and the tree follows the binary search tree rule.
1 <= k <=the number of nodes.- The tree does not have to be balanced. It can be a single chain, so its height can equal its number of nodes.
More Nutanix Phone Screen questions
- Swap Adjacent Linked List NodesPHONE SCREEN · Seen Mar 2025
- Top K Most Frequent ValuesPHONE SCREEN · Seen Mar 2025
- Unique Triplets Summing to ZeroPHONE SCREEN · Seen Sep 2024
- Find the Duplicate in a Read-Only ArrayPHONE SCREEN · Seen Apr 2021
- Kth Largest Element in an ArrayPHONE SCREEN · Seen Feb 2020
- Outline of a Binary TreePHONE SCREEN · Seen Jan 2020
- Print All File and Folder PathsPHONE SCREEN · Seen Dec 2019
- Inorder Predecessor in a BSTPHONE SCREEN · Seen Jan 2019
- K Largest and K Smallest ValuesPHONE SCREEN · Seen Jan 2019
- Odd Numbers Up and BackPHONE SCREEN · Seen Jan 2019
Similar questions at other companies
- Validate a BST with a Custom ComparisonApple · PHONE SCREENApple interview questions
- Find File Paths in a Directory TreeUber · PHONE SCREENUber interview questions
- Delete a Filesystem TreeDatadog · PHONE SCREEN · ONSITE INTERVIEWDatadog interview questions
- Turn a BST Into a Sorted Doubly Linked ListAdobe · PHONE SCREENAdobe interview questions
- Kth Smallest Value in a BSTExpedia · PHONE SCREEN · ONSITE INTERVIEWExpedia interview questions
- Serialize and Deserialize a Binary TreeNVIDIA · PHONE SCREENNVIDIA interview questions
- Binary Tree Preorder TraversalMorgan Stanley · PHONE SCREENMorgan Stanley interview questions
- Binary Tree Inorder TraversalBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Recover a Tree from Preorder Depth EncodingSuperhuman · PHONE SCREENSuperhuman interview questions
- Filesystem Entity Total SizeGoogle · ONSITE INTERVIEWGoogle interview questions