Convert Sorted Array to Binary Search Tree

Easy#108build a tree

You get an array of numbers sorted in increasing order. Build a binary search tree from all of them that is height-balanced: at every node, the heights of the two subtrees differ by at most one. Any such tree will do. Our array: [-7, -2, 0, 3, 8, 11] — one answer, level by level, is [0, -7, 8, none, -2, 3, 11].

108 Convert Sorted Array to Binary Search TreeWalkthrough · 1×

Example: build a balanced binary search tree from the sorted array [-7, -2, 0, 3, 8, 11]: the middle is the root, the halves are the subtrees.

0-71-2203348511
not in the tree yetrange of the current callmiddle: the current nodewaiting for a subtreesubtree built

Build the tree from the whole array: build(0, 5)

01/47
restart · back · play · step
Speed
1function sortedArrayToBST(nums):
2 return build(0, len(nums) - 1)
3
4function build(lo, hi):
5 if lo > hi:
6 return none
7 mid = (lo + hi) / 2 // rounded down
8 node = new node(nums[mid])
9 node.left = build(lo, mid - 1)
10 node.right = build(mid + 1, hi)
11 return node
state
lo
–
hi
–
mid
–
node
–
click a step to go back

← → step · space play/pause

Why it works

  1. Everything left of the middle is smaller and everything right of it is larger, so the middle as the root with the halves below it is a search tree, and the same holds inside each half.
  2. The two halves differ in size by at most one value, so their trees differ in height by at most one: the whole tree is balanced.
  3. With an even count either middle works; rounding down just puts the extra value on the right, as with -7 and -2.

Complexity

Time O(n): each value becomes a node once, and a call does O(1) work besides its two calls. Memory O(log n) besides the tree: the call stack is as deep as the balanced tree is tall.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.