[4.3] Sorted array to binary tree

1. Example

               12"3"456
                /             \
               /               \
    "1"2                    4"5"6
 X     "2"               "4"    "6"
        X  X            X  X   X  X

create a binary tree with minimal height = > balanced

The idea is that mid as a root

NOTE: sorted array => array[mid]
SET ROOT FIRST then root left root right
TreeNode root = new TreeNode(array[mid]); 

root.left = addTotree(array, start,mid-1); 

root.right = addToTree(array, mid+1, end); 

return root;

NOTE: sorted linkedlist => linklist[mid] X=> traverse to the first node
SET ROOT left first then root then root.right TreeNode left = helper(list ,start, mid-1);
TreeNode root = new TreeNode(list.get(0).val);// head val

root.left  = left;

list.set( 0, list.get(0).next );

root.right = helper( list, m+1, r );

return root;

idx  012345
       123456
mid=2
0,2-1
             mid = 0
             0, -1 X
             1,1
                 mid =1
                 1,0X
                 2,1X
                root =2
            root =1 root.left = X root.right = 2
2+1, 5
          mid = 4
          3,3
                mid = 3
                root = 4
          5,5
              mid =5
              root =6
          root = 5 root.left =4 root.right =6
root =3 root.left = 1..... root.right = 5



http://algorithms.tutorialhorizon.com/sorted-array-to-binary-search-tree-of-minimal-height/

http://msoe.us/taylor/tutorial/cs2852/bst
http://algorithms.tutorialhorizon.com/given-a-sorted-singly-linked-list-array-convert-it-into-a-balanced-binary-search-tree/

2. Implementation

public static TreeNode createMinimalBST(int[] array)
{



       if (array == null || array.elgnth == 0)
          return null;



       return addToTree(array, 0, array.length-1);



}


private static TreeNode addToTree(int[] array, int start, int end)
{



       if (start > end)
          return null;



       
       int mid = (start+end)/2;
       TreeNode root = new TreeNode(array[mid]);
       root.left = addTotree(array, start,mid-1);
       root.right = addToTree(array, mid+1, end);
       return root;




}

//public static TreeNode createMinimalBST(int[] array)
public static TreeNode createMinimalBST(ListNode head)
{




       //if (array == null || array.elgnth == 0)
       if (head == null)
          return null;



 
       // NOTE: count to know the length
       ListNode cur = head;
       int length = 0;
       while ( cur != null)
       {
              cur = cur.next;
              length++;
       }





       List list  = new ArrayList();
       list.add(head);





       //return addToTree(array, 0, array.length-1);
       return addToTree(list,0,length-1);




}


private static TreeNode addToTree(int[] array, int start, int end)
{




       if (start > end)
          return null;



       
       int mid = (start+end)/2;
 



       //TreeNode root = new TreeNode(array[mid]);
       //root.left = addTotree(array, start,mid-1);
       //root.right = addToTree(array, mid+1, end); 



   
       TreeNode left = helper(list ,start, mid-1);// first node left is null
       TreeNode root = new TreeNode(list.get(0).val); // first node = head val
       root.left = left;
       list.set( 0, list.get(0).next );
       root.right = addToTree(list, m+1,r);





       return root;




}

3. Similar Ones