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
2
3
4
5
6
7
8
9
Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3 9
/ /
-10 5

Analysis

Methods:

  1. 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
      23
      public 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;
      }
      Time: $O(N)$ since we need to create each node.
      Space: $O(\log{N})$
  2. 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
      36
      public 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;
      }
      Time: $O(N)$
      Space: $O(\log{N})$

What About List?

Naive Recursion

Use right-leaning findMid.

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
36
37
38
39
40
41
42
43
44
45
46
public TreeNode sortedListToBST(ListNode head) {
return construct(head);
}

private TreeNode construct(ListNode node) {
if (node == null) {
return null;
}
if (node.next == null) { // one item
return new TreeNode(node.val);
}
// split
// [] []
// mid
//
// [] [] []
// mid
ListNode mid = findMid(node); // a left-leaning mid
ListNode rest = mid.next; // mid.next = null; // optional
// new mid node
TreeNode midNode = new TreeNode(mid.val);

midNode.left = construct(node);
midNode.right = construct(rest); // may be null

return midNode;
}

// right-leaning
private ListNode findMid(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head;
ListNode prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
if (prev != null) {
prev.next = null;
}
return slow;
}

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
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
36
37
38
39
40
private ListNode head;

public TreeNode sortedListToBST(ListNode head) {
int size = findSize(head);
this.head = head;
return convertListToBST(0, size - 1);
}

// Inorder Traversal
private TreeNode convertListToBST(int lo, int hi) {
if (lo > hi) {
return null;
}
int mid = lo + (hi - lo) / 2;

// Traverse left
TreeNode leftNode = convertListToBST(lo, mid - 1);

// Once left half is traversed, process the current node
TreeNode root = new TreeNode(this.head.val);
root.left = leftNode; // at first it is null

// Maintain the invariance mentioned in the algorithm
this.head = this.head.next;

// Recurse on the right hand side
node.right = this.convertListToBST(mid + 1, hi);

return root;
}

private int findSize(ListNode head) {
ListNode p = head;
int count = 0;
while (p != null) {
p = p.next;
count += 1;
}
return count;
}

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