LeetCode Convert Sorted Array to Binary Search Tree: Linear Time Approach

Overview

LeetCode Convert Sorted Array to Binary Search Tree could be tackled by a top down linear approach to build the binary search tree in a recursive way.

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.

Analysis: Top Down Linear Time Approach

We can build the tree in a top down scheme. Initially, find the middle elements in the array at the position N/2, this is our root in the balanced BST, we make a node for this element, we recursively call the procedure to build the left subtree and the right subtree. Since we can get the position of the root node in const time, the total time complexity would be linear O(N). And regarding with the space complexity, we need O(logN) for the recursive call parameters and O(N) for the final constructed Binary Search Tree, the it would be totally O(N). The following code is accepted by LeetCode OJ to pass this Convert Sorted Array to Binary Search Tree problem:

class Solution {
    public:
        TreeNode *sortedArrayToBSTInner(const vector<int> &num, int l, int r) {
            if (l > r) return NULL;
            if (l == r) {
                TreeNode *root = new TreeNode (num[l]);
                return root;
            }

            int mid = l + (r - l) / 2;
            TreeNode *root = new TreeNode(num[mid]);
            root->left  = sortedArrayToBSTInner(num, l, mid - 1);
            root->right = sortedArrayToBSTInner(num, mid + 1, r);
            return root;
        }

        TreeNode *sortedArrayToBST(vector<int> &num) {
            return sortedArrayToBSTInner(num, 0, num.size() - 1);
        }
};

**Follow up question: **Can we do it in an iterative way?

Summary

LeetCode Convert Sorted Array to Binary Search Tree could be tackled by a top down linear approach to build the binary search tree in a recursive way.

Written on April 17, 2013