Sponsored
Sponsored
This approach selects the middle element of the current array (or subarray) to ensure a balanced partitioning of elements, thus maintaining the height balance of the BST.
The middle element of the array becomes the root of the BST (or subtree), and the same operation is recursively applied to the left and right halves of the array to form the left and right subtrees respectively.
Time Complexity: O(n), where n is the number of elements in the array, because each element is visited once.
Space Complexity: O(log n) due to the recursion stack in a balanced tree scenario.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10struct TreeNode* newNode(int value) {
11 struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
12 node->val = value;
13 node->left = NULL;
14 node->right = NULL;
15 return node;
16}
17
18struct TreeNode* sortedArrayToBSTHelper(int* nums, int left, int right) {
19 if (left > right) {
20 return NULL;
21 }
22 int mid = left + (right - left) / 2;
23 struct TreeNode* node = newNode(nums[mid]);
24 node->left = sortedArrayToBSTHelper(nums, left, mid - 1);
25 node->right = sortedArrayToBSTHelper(nums, mid + 1, right);
26 return node;
27}
28
29struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
30 return sortedArrayToBSTHelper(nums, 0, numsSize - 1);
31}This C program defines a TreeNode structure and uses a helper function to recursively build the BST from the middle of the array. The recursive calls split the array into two halves to build the left and right subtrees.