Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Sorted Array to Binary Search Tree of Minimal Height

Objec­tive: Given a sorted array with unique ele­ments, Cre­ate a binary search tree with min­i­mal height.

Why min­i­mal height is important :

We can do the lin­ear scan to the array and make the first ele­ment as root and insert all other ele­ments into the tree but in that case tree will be skewed , which means all the nodes of the tree will be on the one side of the root so the height of the tree will be equal to the num­ber of ele­ments in the array. So here our objec­tive is to keep the tree bal­anced as much as possible.

What is bal­anced Tree: A bal­anced tree is a tree in which dif­fer­ence between heights of sub-trees of any node in the tree is not greater than one. To read more about bal­anced tree, click here

Input: A one dimen­sional array

Out­put: Binary Search Tree of Min­i­mal Height

Exam­ple:

Sorrted Array To BST Example

Sor­rted Array To BST Example

Approach:

Recur­sion:

  • Get the mid­dle of the array
  • make it as root. (By doing this we will ensure that half of the ele­ments of array will be on the left side of the root and half on the right side.)
  • Take the left half of the array, call recur­sively and add it to root.left.
  • Take the right half of the array, call recur­sively and add it to root.right.
  • return root.
Array To BST Recursion

Array To BST Recursion

Com­plete Code:

Out­put:

Tree Display :
2 3 6 7 8 9 12 15 16 18 20

You may also like...

  • San­tosh Kumar

    http://www.youtube.com/watch?v=VCTP81Ij-EM Here is video for con­vert­ing sorted array to bal­anced BST.

  • Rahul Shukla

    http://www.youtube.com/watch?v=VCTP81Ij-EM Here is video for con­vert­ing sorted array to bal­anced BST.

  • Archit

    // code in Java for the above problem

    pub­lic class Bina­ry­Tree {
    sta­tic Node root;

    sta­tic class Node {
    Node left;
    Node right;
    int data;

    Node(int data){
    this.data = data;
    left = right = null;
    }
    }

    sta­tic Node sortedArrayToBST(int[] a , int start , int end){
    if(start > end){
    return null;
    }
    int mid = (start+end)/2;
    Node node = new Node(a[mid]);
    node.left = sortedArrayToBST(a,start,mid-1);
    node.right = sortedArrayToBST(a,mid+1,end);
    return node;
    }

    sta­tic void preOrder(Node node){
    if(node == null){
    return;
    }
    System.out.println(node.data);
    preOrder(node.left);
    preOrder(node.right);
    }

    pub­lic sta­tic void main(String…args){
    int[] a = {1,2,3,4,5,6,7};
    root = sortedArrayToBST(a,0,a.length-1);
    preOrder(root);
    }

    }