How to convert a sorted array to a binary search tree

Given sorted array in ascending order, return a height-balanced binary search tree

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than 1

 

Example 1

Input:   [1, 2, 3]

Output:      2
            / \
           1   3

Example 2

Input:   [0, 1, 2, 3] 

Output:       1
             / \
            0   2
                 \
                  3

A tree node is represented like this:

    public class TreeNode
    {
        public int Value;
        public TreeNode Left;
        public TreeNode Right;
    
        public TreeNode(int value)
        {
            Value = value;
        }
    }

Algorithm

A binary Search Tree (BST) is a binary tree where each node has a key and meet the following requirements:

• The left subtree of a node contains nodes with keys smaller than the node's key
• The right subtree of a node contains nodes with keys larger than the node's key
• The left and right subtree are binary search trees

We can use the knowledge that the array is sorted. We can divide the array into two equal parts and assign the mid-value as a root node. The elements in the array to the left of the mid-value would the left subtree and the elements in the array to the right of the mid-value would the right subtree.

• get the middle of the array and make it as root
• recursively do the same for the left half and the right half
  • get the middle of the left half and make it the left child of the root
  • get the middle of the right half and make it the right child of the root

 

Code

    public TreeNode Convert(int[] array)
    {
        if (array == null || array.Length == 0)
        {
            return null;
        }

        return Convert(array, 0, array.Length - 1);
    }

    private static TreeNode Convert(int[] array, int lo, int hi)
    {
        if (lo > hi)
        {
            return null;
        }

        int mid = lo + (hi - lo) / 2;
        var root = new TreeNode(array[mid]);
        root.Left = Convert(array, lo, mid - 1);
        root.Right = Convert(array, mid + 1, hi);
        return root;
    }

Time Complexity: O(n)