Arrays: Convert a sorted array into a binary search tree using recursive approach


In this article, we will convert the given sorted array into a binary search tree and print in preorder traversal of that tree

 
Approach
  1. Since the approach is recursive, the idea is to find the middle element of the given sorted array and make it as a root
  2. Then find the middle element for the left side of array and make it as the left child of the root element
  3. Similarly find the middle element of the right side of array and make it as the right child of the root element
  4. Do this recursively
  5. Finally print the binary tree in preorder traversal
 
Complexity

Time Complexity : O(n) , since we are visiting each element of array exactly once
Space Complexity: O(1)

 
Java Code
class ConvertSortedArrayToBSTRecursive{
	
        class Node {
             
            int data;
            Node left, right;
            Node(int d) {
                data = d;
                left = right = null;
            }
        }	
    
        static Node root;
    
        Node arraytoBst(int array[], int start, int end) {
     
            if (start > end) {
                return null;
            }
    
            int mid = (start + end) / 2;
            Node node = new Node(array[mid]);
            
            node.left = arraytoBst(array, start, mid - 1);
            node.right = arraytoBst(array, mid + 1, end);
            
            return node;
        }
    
        void preOrder(Node node) {
            if (node == null) {
                return;
            }
            
            System.out.print(node.data + " ");
            
            preOrder(node.left);
            preOrder(node.right);
        }
         
        public static void main(String[] args) {
            ConvertSortedArrayToBSTRecursive a = new ConvertSortedArrayToBSTRecursive();
            int sortedArray[] = new int[]{1, 2, 3, 4, 5, 6, 7};
            
            System.out.println("Sorted array: ");
            for(int element: sortedArray){
                System.out.print(element + " ");
            }
            
            int n = sortedArray.length;
            root = a.arraytoBst(sortedArray, 0, n - 1);
            System.out.println();
            System.out.println("Preorder traversal of constructed BST: ");
            a.preOrder(root);
        }
    
  }
 
Output

Sorted array:
1 2 3 4 5 6 7
Preorder traversal of constructed BST:
4 2 1 3 6 5 7



Thanks for feedback.



Read More....
Check if an array is a min heap
Print the elements of an array
Find the kth largest element in the array
Find the kth smallest element in the array
Merge two sorted arrays