Leetcode 1382: Balance a Binary Search Tree
Given the root of a binary search tree (BST), return a balanced BST containing the same node values. A balanced BST is one where the depth of the left and right subtrees of every node never differ by more than 1.
Problem
Approach
Steps
Complexity
Input: The input is a binary search tree (BST) represented as an array where each element is a node of the tree.
Example: Input: root = [1, null, 2, null, 3, null, 4]
Constraints:
• The number of nodes in the tree is between 1 and 10,000.
• The value of each node is between 1 and 100,000.
Output: The output is a balanced binary search tree (BST) containing the same node values from the input tree. The tree should be balanced in such a way that the difference in height between the left and right subtrees of any node is at most 1.
Example: Output: [2, 1, 3, null, null, null, 4]
Constraints:
• The tree must be balanced according to the problem definition.
Goal: The goal is to return a balanced BST that contains the same node values as the input BST.
Steps:
• 1. Perform an inorder traversal on the BST to get the nodes in sorted order.
• 2. Use the sorted nodes to construct a balanced BST by recursively selecting the middle node as the root and dividing the remaining nodes into left and right subtrees.
Goal: The solution must be efficient enough to handle up to 10,000 nodes.
Steps:
• The solution must be able to handle a large number of nodes (up to 10,000).
• The value of each node is within the range of 1 to 100,000.
Assumptions:
• The input tree is a binary search tree (BST).
• A balanced BST is defined as a tree where the height difference between the left and right subtrees of every node is at most 1.
• Input: Input: root = [1, null, 2, null, 3, null, 4]
• Explanation: The input tree is right-skewed. To balance it, we first extract the nodes in sorted order: [1, 2, 3, 4]. We then construct a new tree with the middle element (2) as the root, and recursively build left and right subtrees from the remaining nodes.
Approach: The approach involves converting the input BST to an inorder array and then using this sorted array to build a balanced BST by recursively selecting the middle element as the root of each subtree.
Observations:
• The tree is unbalanced, and we need to rearrange it to create a balanced structure.
• Inorder traversal of a BST results in a sorted list of node values.
• Once we have the sorted array of nodes, we can use it to recursively build a balanced tree.
Steps:
• 1. Perform an inorder traversal of the tree to collect all node values in sorted order.
• 2. Use the sorted node values to recursively construct a balanced BST. The middle node becomes the root of the tree, and the left and right subtrees are built using the remaining nodes.
Empty Inputs:
• If the tree is empty, return null.
Large Inputs:
• Ensure that the solution handles large trees (up to 10,000 nodes) efficiently.
Special Values:
• The values of the nodes are between 1 and 100,000, which means that balancing the tree should not depend on specific values.
Constraints:
• The solution should not exceed time limits for large trees with up to 10,000 nodes.
class Solution {
vector<int> arr;
public:
TreeNode* balanceBST(TreeNode* root) {
inorder (root);
return reform(0, arr.size()-1);
}
void inorder (TreeNode* root) {
if(root == NULL ) return;
inorder (root->left);
arr.push_back(root->val);
inorder (root->right);
}
TreeNode* reform(int l, int r) {
if (l > r) return NULL;
int mid = (l + r)/2;
TreeNode* node = new TreeNode(arr[mid]);
node->left = reform (l, mid -1);
node->right= reform (mid +1, r);
return node;
}
1 : Class Definition
class Solution {
Define a class Solution where the main logic for balancing the BST will be implemented.
2 : Data Structures
vector<int> arr;
A vector is used to store the elements of the BST during the in-order traversal.
3 : Access Modifiers
public:
The public section of the class where the methods will be defined for solving the problem.
4 : Function Definition
TreeNode* balanceBST(TreeNode* root) {
The balanceBST function receives the root of the tree and balances the BST by calling inorder and reform functions.
5 : Traversal
inorder (root);
Call the inorder function to perform an in-order traversal of the binary tree and store its values.
6 : Return Statement
return reform(0, arr.size()-1);
Invoke the reform function to build a balanced BST using the values stored in arr.
7 : Function Definition
void inorder (TreeNode* root) {
The inorder function is used to traverse the tree in in-order fashion and store the values in the arr vector.
8 : Base Case
if(root == NULL ) return;
Base case for the recursion: if the node is NULL, return immediately.
9 : Traversal
inorder (root->left);
Recursive call to traverse the left subtree of the node.
10 : Store Data
arr.push_back(root->val);
Store the value of the current node in the arr vector.
11 : Traversal
inorder (root->right);
Recursive call to traverse the right subtree of the node.
12 : Function Definition
TreeNode* reform(int l, int r) {
The reform function recursively builds a balanced binary tree using the sorted values stored in arr.
13 : Base Case
if (l > r) return NULL;
Base case for recursion: if the left index exceeds the right, return NULL (no more nodes to add).
14 : Calculate Middle
int mid = (l + r)/2;
Find the middle index of the current range to select the root of the subtree.
15 : Node Creation
TreeNode* node = new TreeNode(arr[mid]);
Create a new tree node with the middle value from the arr vector.
16 : Recursive Call
node->left = reform (l, mid -1);
Recursively build the left subtree with the values between the current left index and mid-1.
17 : Recursive Call
node->right= reform (mid +1, r);
Recursively build the right subtree with the values between mid+1 and the current right index.
18 : Return Statement
return node;
Return the newly created node as the root of the subtree.
Best Case: O(n), where n is the number of nodes in the tree. This occurs because both the inorder traversal and the tree-building steps require O(n) time.
Average Case: O(n) in most cases.
Worst Case: O(n) in all cases.
Description: Both the inorder traversal and the tree reconstruction steps have a time complexity of O(n).
Best Case: O(n) in all cases.
Worst Case: O(n), where n is the number of nodes in the tree. This is due to the storage required for the sorted array of node values.
Description: The space complexity is O(n) due to the space needed for storing the node values during the inorder traversal and the recursive calls.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus