LeetCode: Convert Sorted Array to Binary Search Tree

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

---

We can choose the mid point as the root node each time and put left part as the left subtree and right part as the right subtree recursively.

C++ Code:

/*
 * func: sorted_array_to_BST_helper
 * goal: recursive helper function 
 * @param num: input sorted array
 * @param start: starting index
 * @param end: ending index
 * return: root node
 */
TreeNode *sorted_array_to_BST_helper(vector<int> &num, int start, int end){
    if(start > end){
        return nullptr;
    }
    int mid = start + (end - start)/2;
    TreeNode *root = new TreeNode(num[mid]);
    root->left = sorted_array_to_BST_helper(num, start, mid-1);
    root->right = sorted_array_to_BST_helper(num, mid+1, end);
    return root;
}

/*
 * func: sorted_array_to_BST
 * goal: convert a sorted array to a height balanced BST
 * @param num: input sorted array
 * return: root node of the tree
 */
TreeNode *sorted_array_to_BST(vector<int> &num){
    return sorted_array_to_BST_helper(num, 0, num.size()-1);
}

Python Code:

# func: convert sorted array to balanced BST
# @param num: input sorted list
# @return: root node
def sorted_array_to_BST(num):
    if not num:
        return None

    mid = len(num)/2
    root = TreeNode(num[mid])
    root.left = sorted_array_to_BST(num[:mid])
    root.right = sorted_array_to_BST(num[mid+1:])

    return root