• 0

Sorted array to BST
  • sortedarray
  • array
  • binarysearchtree
  • binarytree
  • recursion
  •   
    subscribe
  • Posted: 7 years ago
  • Edit
  • answers (1)
  • views (4318)

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


Posted Answers

  • Posted: 7 years ago
  • Updated: 7 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;
 }

You need to Sign In to post your solution.