FastPrepBuild a Perfect Binary Search Tree
Problems/Build a Perfect Binary Search Tree

Build a Perfect Binary Search Tree

Expedia logoExpedia● MediumNEW GRADONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report asks to build a binary search tree and adds a follow-up about making it a perfect tree. This exercise keeps that stronger requirement. We chose distinct keys, the limits, and what to return when a perfect tree is not possible for the count. Our version is about 92% the same as the reported question.

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[]) → TreeNode

Examples

Example 1

values = [4,1,7,2,6,3,5]return = [4,2,6,1,3,5,7]
return
4213657

The seven sorted keys form a perfect three-level BST with root 4.

Example 2

values = [1,2,3,4]return = []
return
empty

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
See 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 TreeNode buildPerfectBST(int[] values) {
        // Write your code here.
    }

}
Checking account…