### Sorted array to BST sortedarray array binarysearchtree binarytree recursion    Posted: 5 years ago Edit answers (1) views (3282)

Suppose you are given a sorted array in increasing order. Write a function to convert it into a binary search tree.

 Posted: 5 years ago Updated: 5 years ago 0 0 Edit We can add the elements of the input array to the binary search tree using recursion. Take the middle element of the input array and mark it as the root. Build up left and right sub trees recursively with the left and right sub array of the array. Return the tree. Time complexity = $$O(n)$$. public Node sortedArrayToBST(int[] array) return addToBinarySearchTree(array, 0, array.length - 1); public static TreeNode addToBinarySearchTree(int[] array, int begin, int end){ /* Error */ if (begin > end) return null; /* Take the middle element of the array */ int middle = (begin + end) / 2; /* Middle element is the root of the tree */ TreeNode root = new TreeNode(array[middle]); /* Left subarray is the left subtree */ root.left = addToBinarySearchTree(array, begin, middle-1); /* Similarly, right subarray is the right subtree */ root.right = addToBinarySearchTree(array, middle+1, end); /* Return the tree */ return root; }