108. Convert Sorted Array to Binary Search Tree

Summary

Given an integer array nums whose elements are sorted in ascending order, convert it to a binary search tree.

Approach

Recursion. We start building the tree from the middle number in the sorted array. Then we build the left subtree from the left half and the right subtree from the right half to create a height-balanced tree.

Function

Function build(left, right): If left > right: return None mid = (left + right) // 2 root = TreeNode(nums[mid]) root.left = build(left, mid - 1) root.right = build(mid + 1, right) return root

Complexity

Time Complexity: O(N) because we use each number in nums once. Space Complexity: O(log N) because the recursion stack grows up to the height of the balanced tree.