1+ /*
2+ * Problem: 108
3+ * Name: Convert Sorted Array To BST
4+ * Difficulty: Easy
5+ * Topic: Binary Trees
6+ * Link: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
7+ */
8+
9+ #include < bits/stdc++.h>
10+ using namespace std ;
11+
12+ // Tree Node Implementation
13+ struct TreeNode {
14+ int val;
15+ TreeNode *left;
16+ TreeNode *right;
17+ TreeNode () : val(0 ), left(nullptr ), right(nullptr ) {}
18+ TreeNode (int x) : val(x), left(nullptr ), right(nullptr ) {}
19+ TreeNode (int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
20+ };
21+
22+ // Using only one function
23+ // Time Complexity: O(n)
24+ // Space Complexity: O(n)
25+ TreeNode* sortedArrayToBSTOne (vector<int >& nums) {
26+ if (nums.size () == 0 ) { return nullptr ;}
27+ if (nums.size () == 1 ) { return new TreeNode (nums[0 ]);}
28+ int middleIdx = nums.size () / 2 ;
29+ TreeNode *root = new TreeNode (nums[middleIdx]);
30+ vector<int > leftNums = {nums.begin (), nums.begin () + middleIdx};
31+ vector<int > rightNums = {nums.begin () + middleIdx + 1 , nums.end ()};
32+ root->left = sortedArrayToBSTOne (leftNums);
33+ root->right = sortedArrayToBSTOne (rightNums);
34+ return root;
35+ }
36+
37+ // Using an helper function
38+ // Time Complexity: O(n)
39+ // Space Complexity: O(n)
40+ // This solution uses less memory because it doesn't create the subvectors
41+ TreeNode* sortedArrayToBSTHelper (vector<int >& nums, int left, int right);
42+ TreeNode* sortedArrayToBSTTwo (vector<int >& nums) {
43+ return sortedArrayToBSTHelper (nums, 0 , nums.size ()-1 );
44+ }
45+ TreeNode* sortedArrayToBSTHelper (vector<int >& nums, int left, int right) {
46+ if (left > right) { return nullptr ;}
47+ int middleIdx = left + (right - left) / 2 ;
48+ TreeNode *root = new TreeNode (nums[middleIdx]);
49+ root->left = sortedArrayToBSTHelper (nums, left, middleIdx-1 );
50+ root->right = sortedArrayToBSTHelper (nums, middleIdx+1 , right);
51+ return root;
52+ }
0 commit comments