Build a BST from a list

Problem Deliberately open-ended: given "any list", construct a binary search tree from it. The interviewer expects clarifying questions before code — element type/comparability, duplicates, sortedness, and what "good" means (any BST vs balanced).

Input / Output

• Input: a list of comparable values (assume ints after clarification).
• Output: root of a BST containing all values.

Constraints

• Unsorted input, n up to 10^5. Duplicate policy must be asked (reject, count, or consistent side).

Example

• [7,2,9,1,5] inserted sequentially → BST rooted at 7 with 2(1,5) and 9.

Expected approach

• Unsorted list: sequential BST insert — O(n log n) average, O(n^2) worst on sorted input (say why: degenerate chain). If input is (or can be) sorted: build a height-balanced BST by recursing on the middle element — O(n) after the sort, guaranteeing O(log n) height. Mention self-balancing trees (AVL/red-black) as the production answer for adversarial insert orders. The clarifying-question discipline is a large part of the evaluation.