• 0

Create a minimal height binary search tree from given sorted array of unique integers

Problem description :

Given a sorted (increasing order) array with unique integer elements, create a binary search tree (BST) with minimal height.

Input : A sorted array with unique integer elements // [0, 1, 2, 3, 4, 5, 6]
Output: A binary search tree with minimal height

Below image is an example of a simple binary search tree.

Binary-Search-Tree-in-post-min

Logic :

We will use recursion technique to solve this problem.

  • Find the middle element of an array and insert it into the BST
  • Call the same method on the left side of an array
    • Find the middle element of an array and insert it into the BST
  • Call the same method on the right side of an array
    • Find the middle element of an array and insert it into the BST

Time complexity : O(N Log N)

This post is a follow-up of Create a binary search tree in javascript. I recommend reading that first, as the following code uses the method from it.

Solution :


Learn More :

  • CTCI_6_4.2