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})$