DSA interview question

BST Basics: Build a Height-Balanced BST from a Sorted Array

Easy · Algorithms · Topics: bst, theory

The problem

A product catalogue receives item IDs already sorted and must load them into a binary search tree for fast lookups. In a BST, every node's left subtree holds smaller keys and its right subtree larger keys, so an inorder traversal is sorted. Lookups cost the tree's height, so the tree should be height-balanced: at every node, the two subtree heights differ by at most 1. Making the middle element the root puts half the keys on each side, and recursing on both halves builds the whole balanced BST.

Example: [-10, -3, 0, 5, 9] → [0, -10, 5, null, -3, null, 9].

Function signature

TreeNode* sortedArrayToBST(const vector<int>& nums);  // nums strictly increasing

Test cases

Input	Output (level order)	Explanation
`[-10, -3, 0, 5, 9]`	`[0, -10, 5, null, -3, null, 9]`	0 is the middle
`[1, 2, 3, 4, 5, 6, 7]`	`[4, 2, 6, 1, 3, 5, 7]`	A perfect tree
`[1, 3]`	`[1, null, 3]`	With an even length, take the left middle
`[7]`	`[7]`
`[]`	`[]`

(Confirm: any height-balanced BST with these keys is acceptable; the output shown uses the left-middle choice.)

How interviewers phrase it

"Given an integer array sorted in ascending order, convert it to a height-balanced binary search tree" (LeetCode 108), usually as the entry point to BSTs.

Clarifying questions to ask

Strictly increasing, no duplicates? (Yes.)
Any balanced BST acceptable? (Yes.)
What does height-balanced mean? (Subtree heights differ by at most 1 at every node.)

Follow-ups to expect

"What is the BST property?"
"Why pick the middle?"
"Why does balance matter?"
"What about a sorted linked list?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview