Convert Sorted Array to Binary Search Tree

Question

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Answer 1

Hint:
This question is highly recursive in nature. Think of how binary search works.

An example of a height-balanced tree. A height-balanced tree is a tree whose subtrees differ in height by no more than one and the subtrees are height-balanced, too.

Solution:
If you would have to choose an array element to be the root of a balanced BST, which element would you pick? The root of a balanced BST should be the middle element from the sorted array.

You would pick the middle element from the sorted array in each iteration. You then create a node in the tree initialized with this element. After the element is chosen, what is left? Could you identify the sub-problems within the problem?

There are two arrays left -- The one on its left and the one on its right. These two arrays are the sub-problems of the original problem, since both of them are sorted. Furthermore, they are subtrees of the current node's left and right child.

The code below creates a balanced BST from the sorted array in O(N) time (N is the number of elements in the array). Compare how similar the code is to a binary search algorithm. Both are using the divide and conquer methodology.

BinaryTree* sortedArrayToBST(int arr[], int start, int end) {
    if (start > end) return NULL;
    // same as (start+end)/2, avoids overflow.
    int mid = start + (end - start) / 2;
    BinaryTree *node = new BinaryTree(arr[mid]);
    node->left = sortedArrayToBST(arr, start, mid-1);
    node->right = sortedArrayToBST(arr, mid+1, end);
    return node;
}

BinaryTree* sortedArrayToBST(int arr[], int n) {
    return sortedArrayToBST(arr, 0, n-1);
}

Further Thoughts:
Consider changing the problem statement to "Converting a singly linked list to a balanced BST". How would your implementation change from the above?

Check out my next post: Convert Sorted List to Balanced Binary Search Tree (BST) for the best solution.

Answer 2

Use recursive method to solve this question.

TreeNode *sortedArrayToBST(vector<int> &num) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (num.size() == 0) {
        return NULL;
    }

    if (num.size() == 1) {
        TreeNode *root = new TreeNode(num[0]);
        return root;
    }

    std::vector<int> left_tree(num.begin(), num.begin() + num.size()/2);
    std::vector<int> right_tree(num.begin() + num.size()/2 + 1, num.end());

    TreeNode *root = new TreeNode(num[num.size()/2]);
    root->left = sortedArrayToBST(left_tree);
    root->right = sortedArrayToBST(right_tree);

    return root;
}

Convert Sorted Array to Binary Search Tree

Follow this question

Welcome to LeetCode

Related questions