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.

2 comments:

  1. Nevertheless once you have mastered the art of working there is no better way to make sure Forex Trading Software cost-effective protection. I spoke with one efficient Currency trading trader who described his working experience like having my very own personal money device.

    ReplyDelete
  2. Native Trader System is genuinely easy to use and it’s been tested for more than a year. People with virtually no trading experience and starting out with very little money are now making some VERY SERIOUS MONEY. THIS is no scam. And they’re not selling anything. You could be seeing HUGE profits on AUTOPILOT. Native Trader System is all you need! No more promises, pure profit only! Don’t miss your chance to become successful today with Native Trader System!

    ReplyDelete