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 Answers

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.