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
Post a Comment