Convert Sorted Array to Binary Search Tree LeetCode solution in C++

1
class Solution {
2
 public:
3
  TreeNode *sortedArrayToBST(vector<int> &nums) {
4
    int n = nums.size();
5
    if (n == 0) // if no elements are present
6
      return NULL;
7
    if (n == 1)                     // if only one element is present
8
      return new TreeNode(nums[0]); // create the root node with that element
9

10
    int mid = n / 2; // finding the position of the middle element in the array
11
    TreeNode *root = new TreeNode(nums[mid]); // create root node with mid element
12

13
    vector<int> l(nums.begin(), nums.begin() + mid);   // left subarray
14
    vector<int> r(nums.begin() + mid + 1, nums.end()); // right subarray
15

16
    // using recursion to form the rest of the nodes :
17

18
    // the left nodes of the root must be smaller than root
19
    root->left = sortedArrayToBST(l);
20

21
    // the right nodes of the root must be greater than root
22
    root->right = sortedArrayToBST(r);
23

24
    return root;
25
  }
26
};