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

Kth Smallest Value in a BST

Expedia logoExpedia● MediumINTERNPHONE SCREENONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The interviewer asked for the k-th smallest number in a binary search tree, and said there were 2 ways: 1. an inorder traversal, 2. your own stack that copies the system stack.

The report gives only that line. It does not say whether k starts at 1 or whether you return one value or k values, and it gives no examples or limits. Here, k starts at 1 and you return the single k-th smallest value. Node values are all different, and the tree has at most 10^4 nodes. These are our choices, not from the report.

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

You are given the root of a binary search tree and an integer k. Return the kth smallest value in the tree.

  • For every node, all values in its left subtree are smaller than its own value, and all values in its right subtree are larger.
  • All node values are different.
  • k starts at 1. So k = 1 asks for the smallest value, and k equal to the number of nodes asks for the largest.

Function

kthSmallest(root: TreeNode, k: int) → int

Examples

Example 1

root = [6,3,8,1,5,null,9]k = 3return = 5
root
631589

The values in sorted order are 1, 3, 5, 6, 8, 9. The third one is 5.

Example 2

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

Each node has only a left child, so the tree is one long chain going left. The smallest value 1 is at the very bottom, and you have to go down the whole chain to reach it.

Example 3

root = [-5,-20,7,null,-10]k = 2return = -10
root
-5-20-107

The values in sorted order are -20, -10, -5, 7. The second one is -10. It is the right child of -20, so it comes after -20 and before the root.

Example 4

root = [12,7,20]k = 3return = 20
root
12720

There are three nodes, so k = 3 asks for the largest value. The values in sorted order are 7, 12, 20, so the answer is 20.

Constraints

  • The tree has from 1 to 10^4 nodes.
  • -10^9 <= node.val <= 10^9
  • All node values are different, and the tree is a valid binary search tree.
  • 1 <= k, and k is at most the number of nodes.

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Filesystem Entity Total SizeGoogle · ONSITE INTERVIEWGoogle interview questions
  • Validate a BST with a Custom ComparisonApple · PHONE SCREENApple interview questions
  • Find File Paths in a Directory TreeUber · PHONE SCREENUber interview questions
  • Render a Comment HierarchyAmazon · ONSITE INTERVIEW
  • Kth Smallest Element in a Binary Search TreeSalesforce · ONSITE INTERVIEWSalesforce interview questions
  • Delete a Filesystem TreeDatadog · PHONE SCREEN · ONSITE INTERVIEWDatadog interview questions
  • Flatten and Reconstruct an Ordered TreeThe Walt Disney Company · ONSITE INTERVIEWThe Walt Disney Company interview questions
  • Inorder, Preorder and Postorder TraversalsAMD · ONSITE INTERVIEWAMD interview questions
  • Turn a BST Into a Sorted Doubly Linked ListAdobe · PHONE SCREENAdobe interview questions
  • Compare N-Ary Tree Leaf SequencesNavan · ONSITE INTERVIEWNavan interview questions

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
  • Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)
All Expedia interview questionsSee Expedia 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…