Sunday, June 12, 2011

How to Build a Balanced Binary Search Tree From an Array

Problem
Create a balanced binary search tree from an array of n elements.

Solution
It's always easier to have an example to follow along with, so let the array below be our case study.


The first step is to sort the array.  The next step is to load the tree with these elements.  A simple way to do it is to use binary search with recursion, except that we're adding an element to the tree instead of 'searching' for it.

  /**
   * Create binary search tree.
   * @param array of elements
   * @return The root of the tree.
   */
  public Node makeTree(String[] array) {
    int low = 0;
    int high = array.length - 1;
    return makeTree(low, high, array);
  }

  /**
   * Create binary search tree.
   * @param low The lowest array position.
   * @param high The highest array position.
   * @param array of elements
   * @return The root of the tree.
   */
  private Node makeTree(int low, int high, String[] array) {
    if (low > high) {
      return null;
    }
    else {
      // Same as (low + high) / 2
      int mid = (low + high) >>> 1;
      Node node = new Node(array[mid]);
      node.left = makeTree(low, (mid - 1), array);
      node.right = makeTree((mid + 1), high, array);
      return node;
    }
  }

The function recursively adds all the elements in the left subtree and then all the elements in the right subtree.  Note that it works for edge cases where the input size is zero or one.  The resulting balanced binary search tree is


Now the next question is, how do we check that the solution is correct?  For this trivial example, we can verify it just by looking at the tree.  We can see that every child on the left is less than its parent, and every child on the right is greater than its parent.

For a large input with hundreds or thousands of elements, it would be too time consuming to draw and visually verify the tree like we did above.  The solution to this proceeding problem will be in a future blog post which will cover preorder, inorder, and postorder tree traversals.

No comments:

Post a Comment