FastPrepKth Smallest Element in a BST
Problems/Kth Smallest Element in a BST

Kth Smallest Element in a BST

Nutanix logoNutanix● MediumINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This was one of the coding questions in a Nutanix infrastructure intern's phone screens in early 2020. The report names it only by a coded problem number, which reads as the classic task of finding the kth smallest value in a binary search tree. The interviewer then asked whether the work could be split across several threads.

The report gives no statement, limits or examples. Here all values are different, and k counts from 1. The tree has at most 10^4 nodes with values between -10^4 and 10^4, and it may be a long chain. The examples are our own. The threads follow-up is discussed in the editorial and is not tested.

Our version is about 80% the same as the reported question.

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) → int

Examples

Example 1

root = [5,3,7,2,4,null,8]k = 4return = 5
root
532478

In 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 = 15
root
10201530

Node 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 = -9
root
-3-7-90

The 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 1 and 10^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

Interview reports that mention this question

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)

Nutanix interview experiences

  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
  • Nutanix Intern Debugging Round and Interviews: 25 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // Write your code here.
    }
}
Checking account…