Given a sorted array, build a height balanced binary search tree from it. Height balanced means the two subtrees of every node differ in height by at most 1.
DSA Animator › DSA Revision › Tree › Convert Sorted Array to Binary Search Tree
Remember: the middle element is the root, and each half becomes a subtree. Choosing the middle is what keeps the tree balanced. The video solves Convert Sorted Array to Binary Search Tree (LeetCode 108, Easy) with the Divide and Conquer pattern from the Tree topic, and you can replay every step in the interactive Convert Sorted Array to Binary Search Tree animation.
Given a sorted array, build a height balanced binary search tree from it. Height balanced means the two subtrees of every node differ in height by at most 1.
For minus 10, minus 3, 0, 5, 9, one answer has 0 as the root. Minus 10 and 5 are its children, minus 3 is the right child of minus 10, and 9 is the right child of 5.
Inserting the values one by one, in sorted order, makes a chain going to the right. That is a valid search tree, but it is completely unbalanced.
Pick the middle element as the root. Everything to its left is smaller, so it builds the left subtree. Everything to its right is bigger, so it builds the right subtree. Because both halves have almost the same size, the tree stays balanced. Repeat the same rule on each half until a range is empty.
The full range is index 0 to 4, so the middle is index 2, the value 0, which becomes the root. The left half is minus 10 and minus 3, and its middle is minus 10. The range to the right of minus 10 holds only minus 3, so minus 3 becomes its right child. The right half is 5 and 9, and its middle is 5. 9 becomes the right child of 5. The tree has height 3, and it is balanced.
In code, the helper takes a left and right index, and returns null if left is greater than right. It picks mid as left plus right divided by 2, and creates a node with that value. The left child is built from left to mid minus 1, and the right child from mid plus 1 to right. Every element becomes one node, so it's O of n time.
Remember: the middle element is the root, and each half becomes a subtree. Choosing the middle is what keeps the tree balanced.