Convert Sorted Array to Binary Search Tree in C++ – LeetCode Solution [Easy]

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.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]

Approach

This problem could be solved by recursively finding the middle of the array and making it the root and then following the same procedure for left and right subtree. The idea is similar to creating a binary search tree doing a postorder traversal.

Time Complexity: O(n), where n is the size of array

Pseudocode

Solve (nums, low, high)
1. int mid = (low+high)/2
2. leftTree = Solve (nums, low, mid)
3. rightTree = Solve (nums, mid+1, high) 
4. root = new TreeNode(nums[mid])
5. root->left = leftTree
6. root->right = rightTree
7. return root

Code Implementation

class Solution {
public:
    TreeNode* solve(vector<int>& nums, int low, int high) {
        TreeNode* root = NULL;

        if (low < high) {
            int mid = (low+high)/2;
            TreeNode* leftTree = solve(nums, low, mid);
            TreeNode* rightTree = solve(nums, mid+1, high);
            root = new TreeNode(nums[mid]);
            root->left = leftTree;
            root->right = rightTree;
        }

        return root;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size();
        return solve(nums, 0, n);
    }
};

Output

Your input
[-10,-3,0,5,9]
Output
[0,-3,9,-10,null,5]
Expected
[0,-3,9,-10,null,5]

Practice problems
Convert Sorted Array to Binary Search Tree – LeetCode
Sorted Array to Balanced BST – GeeksforGeeks