How to Convert Sorted Array to Balanced Binary Search Tree?

Given an array of sorted integers, let’s arrange it to a highly balanced binary search tree (BST). The left nodes of a binary search tree are smaller than the root node whilst the right nodes are bigger than the root node. A highly balanced BST is a tree that the depths of both sub trees have no more than 1 difference.

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Recursive Implementation to Convert Sorted Array to BST

The problem can be decomposed recursively by selecting the root node, left node, right node – and attach the left and right node to the root. As the array is already sorted, we can select the middle number as a root so the differences of depths will be no more than one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums, int left, int right) {
        if (left > right) {
            return NULL;
        }
        int mid = left + (right - left) / 2;
        TreeNode* head = new TreeNode(nums[mid]);
        head->left = sortedArrayToBST(nums, left, mid - 1);
        head->right = sortedArrayToBST(nums, mid + 1, right);
        return head;
    }
 
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(nums, 0, nums.size() - 1);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums, int left, int right) {
        if (left > right) {
            return NULL;
        }
        int mid = left + (right - left) / 2;
        TreeNode* head = new TreeNode(nums[mid]);
        head->left = sortedArrayToBST(nums, left, mid - 1);
        head->right = sortedArrayToBST(nums, mid + 1, right);
        return head;
    }

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

Each element in the sorted array is visited exactly once hence the runtime complexity is O(N). The space complexity is O(N) as well e.g. as you will need to allocate N nodes and the cost for recursion is O(logN) – the maximum depth of the BST is O(logN).

Based on the same recursive idea but implemented slightly without the ranges to specify the sub array, the following C++ will slice the original array, creating copies of sub array to pass on to recursive function, and thus less memory and time efficient.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return nullptr;
        int mid = nums.size() / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        if (mid > 0) {
            vector<int> left(begin(nums), begin(nums) + mid);
            root->left = sortedArrayToBST(left);
        }
        if (mid + 1 < nums.size()) {
            vector<int> right(begin(nums) + mid + 1, end(nums));
            root->right = sortedArrayToBST(right);
        }
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return nullptr;
        int mid = nums.size() / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        if (mid > 0) {
            vector<int> left(begin(nums), begin(nums) + mid);
            root->left = sortedArrayToBST(left);
        }
        if (mid + 1 < nums.size()) {
            vector<int> right(begin(nums) + mid + 1, end(nums));
            root->right = sortedArrayToBST(right);
        }
        return root;
    }
};

The first implementation took 16ms to pass all test cases while the second implementation took 20ms which is about 25% times slower – as to create copies of sub vectors require O(N) – thus the overall complexity os O(N^2).

–EOF (The Ultimate Computing & Technology Blog) —