108. Convert Sorted Array / List to Binary Search Tree

Reference: LeetCode EPI 14.8
Difficulty: EasyMedium

Problem

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Analysis

Methods:

1. Recursion
• Be careful of the base case.

Time: $O(N)$ since we need to create each node.
Space: $O(\log{N})$

1. Iteration
• Just simulate the recursion process.

Time: $O(N)$
Space: $O(\log{N})$

Naive Recursion

Use right-leaning findMid.

Time:

• Best: $O(N\log{N})$
• Worst: $O(N^2)$

Space: $O(\log{N})$

Conversion to Array

Or use recursion and list-to-array conversion. This method increases the space to $O(N)$.

Inorder Simulation

Or use the idea of inorder simulation:

• Calculate the length of the list.
• Calculate the middle node by (lo + hi) / 2, but actually we don’t need to use the middle node.
• We make recursive calls on the two halves.
• Recurse on the left half by using lo, mid - 1, until we meet the left most node.
• The invariance that we maintain is that whenever we are done building the left half of the BST, the head pointer in the linked list will point to the root node or the middle node. We update it by head = head.next.
• Then we recurse on the right hand side using mid + 1, end.

Time: $O(N)$
Space: $O(\log{N})$

Comment
Junhao Wang
a software engineering cat