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;
}

Answer 3

use recursive function

TreeNode *sortedArrayToBST(vector<int> &num) {
    return helper(num, 0, num.size());
}
TreeNode *helper(vector<int> &num, int start, int end) {
    int M = end-start;
    if (M < 1) {
        return NULL;
    } else if(M ==1) {
        return new TreeNode(num[start]);
    } 
    TreeNode* root = new TreeNode(num[start+M/2]);
    TreeNode* left = helper(num, start, start+M/2);
    TreeNode* right = helper(num, start+M/2+1, end);
    root->left = left;
    root->right = right;
    return root;
}

Answer 4

class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        int len = num.size();
        TreeNode *root;
        if(len==0)return NULL;
        if(len==1){root=new TreeNode(num[0]);return root;}
        return DFS(0,len-1,root,num);
    }
    TreeNode *DFS(int left,int right,TreeNode *root,vector<int> &num)
    {
        if(left>right)
        {
            return NULL;
        }
        if(left==right)
        {
            root = new TreeNode(num[left]);
            return root;
        }
        int mid = left+((right-left)>>1);
        root = new TreeNode(num[mid]);
        if(left<mid)root->left = DFS(left,mid-1,root->left,num);
        if(mid<right)root->right = DFS(mid+1,right,root->right,num);
        return root;
    }
};

Answer 5

public class Solution {

public TreeNode sortedArrayToBST(int[] num) {
    if (num.length == 0) return null;
    return toBST(num,0,num.length-1);
}

private TreeNode toBST(int[] num,int s, int e){
    TreeNode res = new TreeNode(0);        
    if(s==e)
        return new TreeNode(num[s]);
    else if(e-s == 1){ //Case for two elements
        res.val = num[e];
        res.left = new TreeNode(num[s]);
    }else if( (e-s)%2 == 0){ //Case for odd number elements
        res.val = num[(e+s)/2];
        res.left = toBST(num,s,(e+s -2)/2 );
        res.right = toBST(num,(e+s +2)/2,e);
    } else{ //Case for even number elements
        res.val = num[(e+s+1)/2];
        res.left = toBST(num,s,(e+s-1)/2);
        res.right = toBST(num,(e+s+3)/2,e);
    }
    return res;
}

}

Answer 6

TreeNode *sortedArrayToBST(vector<int> &num) {

    if(num.size() == 0) {
       return NULL;
    }
    if(num.size() == 1) {
        return new TreeNode(num[0]);
    }
    int middle = num.size()/2;
    TreeNode *root = new TreeNode(num[middle]);
    vector<int> left(num.begin(), num.begin() + middle );
    vector<int> right(num.begin() + middle + 1 , num.end());
    root->left = sortedArrayToBST(left);
    root->right = sortedArrayToBST(right);
    return root;
}

Answer 7

class Solution {
public:
    TreeNode* CreateNode(vector<int>& num, int lo, int hi)
    {
        if (lo == hi)
        {
            return new TreeNode(num[lo]);
        }
        int mid = lo + ((hi-lo) / 2);
        TreeNode* root = new TreeNode(num[mid]);
        if (mid-1 >= lo)
        {
            root->left = CreateNode(num, lo, mid-1);
        }
        if (mid + 1 < num.size())
        {
            root->right = CreateNode(num, mid+1, hi);
        }
        return root;
    }

    TreeNode* sortedArrayToBST(vector<int> &num)
    {
        if (0 == num.size())
        {
            return NULL;
        }
        TreeNode* root = CreateNode(num, 0, num.size()-1);
        return root;
    }
};

Answer 8

public TreeNode sortedArrayToBST(int[] num) {
    if( num.length < 1 ){
        return null;
    }
    int mid = (int) num.length/2;
    TreeNode root = new TreeNode( num[mid] );
    root.left = sortedArrayToBST(Arrays.copyOfRange(num, 0, mid));
    root.right = sortedArrayToBST(Arrays.copyOfRange(num,mid+1,num.length));
    return root;
}

Answer 9

public static Node sortedArrayToBST(int[] input, int start, int end) 
{
    //base cases
    if (input == null || start > end)
    {
        return null;
    }

    if (start==end)
    {
        return new Node(input[start]);
    }

    int middleIndex = (start+end)/2;
    int meanVal = input[middleIndex];
    Node root = new Node(meanVal);

    root.leftChild = sortedArrayToBST(input, start, middleIndex-1);
    root.rightChild = sortedArrayToBST(input, middleIndex+1, end);

    return root;
}

Convert Sorted Array to Binary Search Tree

Follow this question

Welcome to LeetCode

Related questions