Convert sorted array to balanced binary search tree

In this post ,  we will see how to convert sorted array to balanced binary search tree.

Algorithm:

You might know that inorder traversal of binary search tree results in sorted array. We will use this property to convert sorted array to balanced binary search tree, so middle element of array or sub array will always be root for that array or subarray.
  • Initialise two variables start and end with 0 and arr.length -1.
  • Find middle element of array using start and end.
  • Make middle element root element of tree.
  • Recursively traverse left subtree, find middle and make it root node of left subtree 
  • Recursively traverse right subtree, find middle and make it root node of right subtree.

Java code to convert sorted array to balanced binary search tree:

package org.arpit.java2blog;

public class BinarySearchTreeMain {
 public static class TreeNode {
  int data;
  TreeNode left;
  TreeNode right;

  TreeNode(int data) {
   this.data = data;
  }
 }

 public static void preOrder(TreeNode root) {
  if (root == null)
   return;
  System.out.print(root.data + " ");
  preOrder(root.left);
  preOrder(root.right);
 }

 public static void main(String[] args) {

  // Creating a binary search tree
  int arr[]={10,20,30,40,50,60,70,80,90};
  TreeNode rootNode = createBinarySearchTreeFromSortedArray(arr,0,arr.length-1);  
  
  System.out.println("Preorder traversal of created binary search tree :");
  preOrder(rootNode);

 }

 public static TreeNode createBinarySearchTreeFromSortedArray(int[] arr,int start,int end) {
    if (start > end) {
             return null;
         }
  
         /* Get the middle element and make it root */
         int mid = (start + end) / 2;
         TreeNode node = new TreeNode(arr[mid]);
  
         /* Recursively construct the left subtree and make it
          left child of root */
         node.left = createBinarySearchTreeFromSortedArray(arr, start, mid - 1);
  
         /* Recursively construct right subtree and make right child of the root */
         node.right = createBinarySearchTreeFromSortedArray(arr, mid + 1, end);
          
         return node;
 }
}
When you run above program, you will get below output:
Preorder traversal of created binary search tree :
50 20 10 30 40 70 60 80 90 

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012