Sorted List to Balanced BST
Turn a sorted singly linked list into a height-balanced binary search tree. The harness hands you a forward-only iterator over the values plus the count n; do not copy the values into an array, and do not walk the list repeatedly to find middles.
Build the subtree for index range [lo, hi] with root at mid = floor((lo + hi) / 2), so the result is deterministic: for 1 → 2 → 5 → 6 → 8 → 10 → 19 the root is 6.
sortedListToBst(iterator over [1, 2, 5, 6, 8, 10, 19], 7)
6
/ \
2 10
/ \ / \
1 5 8 19Return the root node; nodes have val, left and right. The harness serialises the tree in level order with null for missing children (trailing nulls trimmed): [6, 2, 10, 1, 5, 8, 19].
Hints
Hint 1
Simulate an in-order traversal: build(lo, hi) recursively builds the left subtree for [lo, mid − 1], then takes the next value from the iterator as the root, then builds the right subtree — the values arrive in exactly in-order sequence.
Hint 2
The recursion depth is O(log n) for a balanced build, and the iterator is consumed exactly once. The O(n log n) find-the-middle version is what to say first, then improve.