Kth Smallest Value in a BST
Updated
Problem statement
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.
kstarts at1. Sok = 1asks for the smallest value, andkequal to the number of nodes asks for the largest.
Function
kthSmallest(root: TreeNode, k: int) → intExamples
Example 1
root = [6,3,8,1,5,null,9]k = 3return = 5The 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 = 1Each 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 = -10The 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 = 20There 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
1to10^4nodes. -10^9 <= node.val <= 10^9- All node values are different, and the tree is a valid binary search tree.
1 <= k, andkis 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)