Sponsored
Sponsored
This approach involves performing an in-order traversal of the binary search tree to collect its node values in sorted order. Since the values are sorted, we can then use the sorted list to construct a balanced binary search tree. The central idea is that the middle element of the sorted list becomes the root of the tree, and recursively the middle element of each sublist becomes the root of the subtrees, thereby ensuring balanced condition.
Time Complexity: O(n), where n is the number of nodes in the BST, for the in-order traversal and subsequent tree construction.
Space Complexity: O(n), for storing the node values in an array.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10void inorder(struct TreeNode* root, int* arr, int* size) {
11 if (!root) return;
12 inorder(root->left, arr, size);
13 arr[(*size)++] = root->val;
14 inorder(root->right, arr, size);
15}
16
17struct TreeNode* buildTree(int* arr, int start, int end) {
18 if (start > end) return NULL;
19 int mid = start + (end - start) / 2;
20 struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
21 node->val = arr[mid];
22 node->left = buildTree(arr, start, mid - 1);
23 node->right = buildTree(arr, mid + 1, end);
24 return node;
25}
26
27struct TreeNode* balanceBST(struct TreeNode* root) {
28 int arr[10000], size = 0;
29 inorder(root, arr, &size);
30 return buildTree(arr, 0, size - 1);
31}The code first defines a TreeNode structure to represent each node of the binary search tree. The inorder function performs the in-order traversal, collecting values into an array. Then, the buildTree function constructs a balanced tree from this array. The balanceBST function orchestrates the process by first collecting nodes and then building and returning the balanced tree.
This alternative approach aims to build a balanced BST directly from the given BST by using a divide-and-conquer strategy. The process involves using in-order traversal to fetch node values, converting it to a sorted array, and recursively constructing the entire balanced tree directly. While the initial step is similar, this approach focuses on minimizing operations by targeting balanced construction upfront.
Time Complexity: O(n), anchored in initial traversal and full reconstruction.
Space Complexity: O(n), stemming from node value arrays.
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void inorder(TreeNode* root, vector<int>& nodes) {
if (!root) return;
inorder(root->left, nodes);
nodes.push_back(root->val);
inorder(root->right, nodes);
}
TreeNode* createBalancedTree(vector<int>& nodes, int start, int end) {
if (start > end) return nullptr;
int mid = (start + end) / 2;
TreeNode* node = new TreeNode(nodes[mid]);
node->left = createBalancedTree(nodes, start, mid - 1);
node->right = createBalancedTree(nodes, mid + 1, end);
return node;
}
TreeNode* balanceBST(TreeNode* root) {
vector<int> nodes;
inorder(root, nodes);
return createBalancedTree(nodes, 0, nodes.size() - 1);
}A strong parallel seen with the C solution, C++ makes use of a vector in inorder to yield sorted node values. Tapping into direct construction via createBalancedTree, the solution remains logically sound in creating balanced trees.