# 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:**

1 | Given the sorted array: [-10,-3,0,5,9], |

## Analysis

**Methods:**

- Recursion
- Be careful of the base case.
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23public TreeNode sortedArrayToBST(int[] nums) {

if (nums == null || nums.length == 0) {

return null;

}

return constructBST(nums, 0, nums.length - 1);

}

private TreeNode constructBST(int[] nums, int lo, int hi) {

if (lo > hi) {

return null;

}

if (lo == hi) {

return new TreeNode(nums[lo]);

}

int mid = lo + (hi - lo) / 2;

TreeNode root = new TreeNode(nums[mid]);

root.left = constructBST(nums, lo, mid - 1);

root.right = constructBST(nums, mid + 1, hi);

return root;

}

- Be careful of the base case.

**Time:** $O(N)$ since we need to create each node.

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

- Iteration
- Just simulate the recursion process.
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36public TreeNode sortedArrayToBST(int[] nums) {

if (nums == null || nums.length == 0) {

return null;

}

int n = nums.length;

// placeholder

TreeNode node = new TreeNode(0);

Stack<TreeNode> stack = new Stack<>();

Stack<Integer> loStack = new Stack<>();

Stack<Integer> hiStack = new Stack<>();

stack.push(node);

loStack.push(0);

hiStack.push(n - 1);

while (stack.size() > 0) {

TreeNode curr = stack.pop();

int lo = loStack.pop();

int hi = hiStack.pop();

int mid = lo + (hi - lo) / 2;

curr.val = nums[mid]; ///

// left

if (lo <= mid - 1) {

curr.left = new TreeNode(0);

stack.push(curr.left);

loStack.push(lo);

hiStack.push(mid - 1);

}

// right

if (mid + 1 <= hi) {

curr.right = new TreeNode(0);

stack.push(curr.right);

loStack.push(mid + 1);

hiStack.push(hi);

}

}

return node;

}

- Just simulate the recursion process.

**Time:** $O(N)$

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

## What About List?

### Naive Recursion

Use right-leaning `findMid`

.

1 | public TreeNode sortedListToBST(ListNode head) { |

**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`

.

1 | private ListNode head; |

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

Comment