Build a Perfect Binary Search Tree
Updated
Problem statement
Use every distinct integer in values exactly once to build a perfect binary search tree: every internal node has two children, every leaf has the same depth, and left-subtree keys are strictly smaller than the node while right-subtree keys are strictly larger.
Return its root. A nonempty perfect tree has 2^h-1 nodes for some positive integer h. If the number of supplied keys cannot form such a tree, return null, serialized as []. Empty input also returns null.
For a feasible count, the sorted keys uniquely determine the perfect BST: its middle key is the root, and the same rule applies recursively to both halves.
Function
buildPerfectBST(values: int[]) → TreeNodeExamples
Example 1
values = [4,1,7,2,6,3,5]return = [4,2,6,1,3,5,7]The seven sorted keys form a perfect three-level BST with root 4.
Example 2
values = [1,2,3,4]return = []Four is not one less than a power of two, so no perfect tree can use all four keys.
Constraints
0 <= values.length <= 511.-1000000000 <= values[i] <= 1000000000.- All supplied keys are distinct.
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
- Top K Pins with Insert and QueryPinterest · PHONE SCREEN
- 3Sum SmallerSalesforce · ONSITE INTERVIEW
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEW
- Insert into a Left-Complete Binary TreeRubrik · ONSITE INTERVIEW
- Maintain a Consistent-Hashing RingCohesity · ONSITE INTERVIEW
- Kth Closest Element in a BSTLinkedIn · ONSITE INTERVIEW
- Shortest Path Between BST NodesGoogle · ONSITE INTERVIEW
- Top-Down Employee Reporting ForestOkta · ONSITE INTERVIEW
- Filesystem Hash TreeCursor · PHONE SCREEN · ONSITE INTERVIEW
- Aggregate Machine TopologyOpenAI · PHONE SCREEN · ONSITE INTERVIEW