p19 — Hints

Open one at a time.

Hint 1 — Reframe

A sorted array IS the inorder traversal of some BST. The question is: which one is height-balanced? Answer: pick the middle as the root; the left half becomes the left subtree, the right half becomes the right subtree. Recurse.

Hint 2 — Divide and Conquer on Indices

Don’t allocate subarrays — pass indices. Write a helper build(lo, hi):

if range empty: return None
mid = (lo + hi) // 2     # or // 2 + 1 — either works
root = TreeNode(nums[mid])
root.left  = build(left half)
root.right = build(right half)
return root

Pick a convention — half-open [lo, hi) or inclusive [lo, hi] — and stick to it. Mixing is the #1 bug here.

Hint 3 — Why Is It Height-Balanced?

The two recursive calls operate on subarrays of size ⌊n/2⌋ and ⌈n/2⌉. These differ by at most 1. By induction, their heights differ by at most 1, so the tree is height-balanced.

Closed form: height = ⌈log₂(n+1)⌉.

Hint 4 — Don’t Insert One-By-One

The tempting wrong approach: “start with an empty BST and insert each element in order.” That gives a fully right-skewed tree (depth N). Mention this as the wrong approach and dismiss it.

Hint 5 — Follow-up: LC 109 (Sorted Linked List → BST)

The naive approach: walk the list into an array, then call this problem’s solution. O(N) time, O(N) extra space.

The elegant approach: inorder pointer trick.

Count list length n.
Recursively build with build(size):
- Build the left subtree first (consuming the first size//2 elements).
- Read the current list pointer’s value → this node’s value; advance the pointer.
- Build the right subtree.

The list pointer is consumed in inorder. O(N) time, O(log N) stack, O(1) extra space.

This trick — “consume the input in inorder during construction” — is the elegant move. Practice it.