Skip to main content

Convert Sorted Array to Binary Search Tree

Problem​

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    TreeNode* createBST(vector<int> nums, int start, int end) {
        if (start > end) return NULL;
        int mid = (start + end) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = createBST(nums, start, mid - 1);
        root->right = createBST(nums, mid + 1, end);
        return root;
    }

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