Sorted Array to Binary Search Tree of Minimal Height

Objective: Given a sorted array with unique elements, Create a binary search tree with minimal height.

Why minimal height is important :

We can do the linear scan to the array and make the first element as root and insert all other elements 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 number of elements in the array. So here our objective is to keep the tree balanced as much as possible.

What is balanced Tree: A balanced tree is a tree in which difference between heights of sub-trees of any node in the tree is not greater than one. To read more about balanced tree, click here

Input: A one dimensional array

Output: Binary Search Tree of Minimal Height

Example:

Sorrted Array To BST Example

Sorrted Array To BST Example

Approach:

Recursion:

  • Get the middle of the array
  • make it as root. (By doing this we will ensure that half of the elements 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 recursively and add it to root.left.
  • Take the right half of the array, call recursively and add it to root.right.
  • return root.
Array To BST Recursion

Array To BST Recursion

Complete Code:

Output:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • Santosh Kumar

    http://www.youtube.com/watch?v=VCTP81Ij-EM Here is video for converting sorted array to balanced BST.

  • Rahul Shukla

    http://www.youtube.com/watch?v=VCTP81Ij-EM Here is video for converting sorted array to balanced BST.

  • Archit

    // code in Java for the above problem

    public class BinaryTree {
    static Node root;

    static class Node {
    Node left;
    Node right;
    int data;

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

    static 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;
    }

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

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

    }

%d bloggers like this: