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

Problem Statement

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

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]


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


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 {
    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);


Your input

Practice problems

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

Leave a Reply