Dare2Solve
To balance a binary search tree (BST), we need to ensure that the depth of the two subtrees of every node never differs by more than one. The best way to achieve this is to use the properties of BSTs and sorted arrays. An inorder traversal of a BST yields a sorted array. By using this sorted array, we can recursively construct a balanced BST.
Inorder Traversal:
Construct Balanced BST:
Implementation:
inorder
: Collects the nodes in an inorder traversal.buildBalancedBST
: Recursively constructs the balanced BST from the sorted array.Time Complexity:
Space Complexity:
This document explains the code for balancing a binary search tree (BST) using JavaScript, function by function.
The inorder
function performs an inorder traversal of the binary tree and stores the nodes in an array. Inorder traversal processes nodes in ascending order for a BST.
var inorder = function (root, nodes) {
if (root === null) return;
inorder(root.left, nodes);
nodes.push(root);
inorder(root.right, nodes);
}
Parameters:
root
: The root of the binary tree.nodes
: An array to store the nodes in sorted order.Process:
root
) is null
, return immediately.nodes
.The solve
function constructs a balanced BST from a sorted array of nodes.
var solve = function (nodes, start, end) {
if (end < start) return null;
const mid = Math.floor((end - start) / 2) + start;
const root = nodes[mid];
root.left = solve(nodes, start, mid - 1);
root.right = solve(nodes, mid + 1, end);
return root;
}
Parameters:
nodes
: The sorted array of nodes.start
: The start index for the current subtree.end
: The end index for the current subtree.Process:
start
is greater than end
, return null
(base case).mid
) of the current subtree.mid
becomes the root of the current subtree.root
.The balanceBST
function balances an unbalanced BST.
var balanceBST = function (root) {
if (root === null) return null;
const inorderTraversal = [];
inorder(root, inorderTraversal);
return solve(inorderTraversal, 0, inorderTraversal.length - 1);
}
Parameters:
root
: The root of the unbalanced BST.Process:
root
is null
, return null
.solve
function to construct a balanced BST from the sorted array of nodes.The provided code efficiently balances an unbalanced BST by utilizing the properties of inorder traversal and sorted arrays. The time complexity is (O(n)), and the space complexity is (O(n)), where (n) is the number of nodes in the tree.
class Solution {
public:
TreeNode* balanceBST(TreeNode* root) {
if (root == nullptr) return nullptr;
vector<TreeNode*> inorderTraversal;
inorder(root, inorderTraversal);
return solve(inorderTraversal, 0, inorderTraversal.size() - 1);
}
private:
void inorder(TreeNode* root, vector<TreeNode*>& nodes) {
if (root == nullptr) return;
inorder(root->left, nodes);
nodes.push_back(root);
inorder(root->right, nodes);
}
TreeNode* solve(const vector<TreeNode*>& nodes, int start, int end) {
if (end < start) return nullptr;
int mid = start + (end - start) / 2;
TreeNode* root = nodes[mid];
root->left = solve(nodes, start, mid - 1);
root->right = solve(nodes, mid + 1, end);
return root;
}
};
class Solution:
def balanceBST(self, root: TreeNode) -> TreeNode:
if root is None:
return None
inorder_traversal = []
self.inorder(root, inorder_traversal)
return self.solve(inorder_traversal, 0, len(inorder_traversal) - 1)
def inorder(self, root: TreeNode, nodes: list) -> None:
if root is None:
return
self.inorder(root.left, nodes)
nodes.append(root)
self.inorder(root.right, nodes)
def solve(self, nodes: list, start: int, end: int) -> TreeNode:
if start > end:
return None
mid = (start + end) // 2
root = nodes[mid]
root.left = self.solve(nodes, start, mid - 1)
root.right = self.solve(nodes, mid + 1, end)
return root
class Solution {
public TreeNode balanceBST(TreeNode root) {
if (root == null) return null;
List<TreeNode> inorderTraversal = new ArrayList<>();
inorder(root, inorderTraversal);
return solve(inorderTraversal, 0, inorderTraversal.size() - 1);
}
private void inorder(TreeNode root, List<TreeNode> nodes) {
if (root == null) return;
inorder(root.left, nodes);
nodes.add(root);
inorder(root.right, nodes);
}
private TreeNode solve(List<TreeNode> nodes, int start, int end) {
if (end < start) return null;
int mid = (end - start) / 2 + start;
TreeNode root = nodes.get(mid);
root.left = solve(nodes, start, mid - 1);
root.right = solve(nodes, mid + 1, end);
return root;
}
}
/**
* @param {TreeNode} root
* @param {TreeNode[]} nodes
*/
var inorder = function (root, nodes) {
if (root === null) return;
inorder(root.left, nodes);
nodes.push(root);
inorder(root.right, nodes);
}
/**
* @param {TreeNode[]} nodes
* @param {number} start
* @param {number} end
* @returns {TreeNode|null}
*/
var solve = function (nodes, start, end) {
if (end < start) return null;
const mid = Math.floor((end - start) / 2) + start;
const root = nodes[mid];
root.left = solve(nodes, start, mid - 1);
root.right = solve(nodes, mid + 1, end);
return root;
}
/**
* @param {TreeNode} root
* @returns {TreeNode|null}
*/
var balanceBST = function (root) {
if (root === null) return null;
const inorderTraversal = [];
inorder(root, inorderTraversal);
return solve(inorderTraversal, 0, inorderTraversal.length - 1);
}