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