Matsushita's Blog

Make a Binary Search Tree from sorted array


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

How to Solve

This problem asks me to create a BST (Binary Search Tree) from array.

What is BST

BST is a tree structure. Each node in BST has two children nodes: right and left. The value of the left node is smaller than root node one and the value of the right node is larger than root node one.

Making the lowest BST

In order to make the BST with minimal height, we have to select root node carefully. Selecting the node with the middle index in range at each state, we can achieve the goal. This idea can be executed by recursive.

Source Code