Convert Sorted Array to Binary Search Tree using C++

 Convert Sorted Array to Binary Search Tree 

Approach

In this problem, a sorted array/vector is given and we have to convert it into a height balanced binary search tree.
We will use recursion to solve this problem. Initially we will create a node with the middle value of the array. we will use recursion to join index=0 to index=middle-1 to left of node and index=middle+1 to index=size of array-1 to right side of node.
At last we will return the node.

    Time Complexity:

        O(n/2) for traversing the array

    Space Complexity:

        O(1)

    C++ Code:

    class Solution {
    public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
       int e=nums.size()-1;
       return bst(0,e,nums);
    }
    TreeNode* bst(int s,int e,vector<int> nums){
        if(s>e)return NULL;
        int mid=(s+e)/2;
        TreeNode* node=new TreeNode(nums[mid]);
        node->left=bst(s,mid-1,nums);
        node->right=bst(mid+1,e,nums);
        return node;
    }
};

Comments

Popular posts from this blog

NITs Gate Vlsi cutoff

Swap Nodes in Pairs using recursion in cpp