📖
Balanced Binary Tree
Tree
~20 min read
5 practice problems
Balanced Binary Tree
Overview
A balanced binary tree is a binary tree in which the height difference between left and right subtrees of every node is at most 1. This property ensures optimal performance for tree operations like search, insertion, and deletion, maintaining O(log n) time complexity.
Key Properties
Definition
A binary tree is balanced if for every node:
- Height of left subtree - Height of right subtree ≤ 1
- Both left and right subtrees are also balanced
Height Balance Factor
The balance factor of a node = Height(left subtree) - Height(right subtree)
- Balance factor ranges from -1 to 1 for balanced trees
Implementation Examples
Basic Tree Node Structure
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}Check if Tree is Balanced
function isBalanced(root) {
function checkBalance(node) {
if (node === null) return 0;
const leftHeight = checkBalance(node.left);
if (leftHeight === -1) return -1; // Unbalanced subtree
const rightHeight = checkBalance(node.right);
if (rightHeight === -1) return -1; // Unbalanced subtree
const balanceFactor = Math.abs(leftHeight - rightHeight);
if (balanceFactor > 1) return -1; // Unbalanced at current node
return 1 + Math.max(leftHeight, rightHeight);
}
return checkBalance(root) !== -1;
}Calculate Height of Balanced Tree
function calculateHeight(root) {
if (root === null) return -1;
const leftHeight = calculateHeight(root.left);
const rightHeight = calculateHeight(root.right);
return 1 + Math.max(leftHeight, rightHeight);
}Types of Balanced Trees
1. AVL Trees
AVL trees are height-balanced binary search trees where the balance factor of every node is -1, 0, or 1.
class AVLNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
this.height = 1; // Height of node
}
}
function getBalanceFactor(node) {
if (node === null) return 0;
return getHeight(node.left) - getHeight(node.right);
}
function getHeight(node) {
if (node === null) return 0;
return node.height;
}
function updateHeight(node) {
if (node !== null) {
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
}2. Red-Black Trees
Red-black trees maintain balance through color properties and rotations.
Balance Factor Analysis
Balance Factor Calculation
function getBalanceFactor(node) {
if (node === null) return 0;
return getHeight(node.left) - getHeight(node.right);
}
function getHeight(node) {
if (node === null) return 0;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}Balance Factor Ranges
- Perfectly Balanced: Balance factor = 0
- Left Heavy: Balance factor > 0 (left subtree taller)
- Right Heavy: Balance factor < 0 (right subtree taller)
- Unbalanced: |Balance factor| > 1
Common Operations
Insertion in Balanced Tree
function insert(root, val) {
// Standard BST insertion
if (root === null) return new TreeNode(val);
if (val < root.val) {
root.left = insert(root.left, val);
} else if (val > root.val) {
root.right = insert(root.right, val);
}
// Rebalance if needed
return rebalance(root, val);
}
function rebalance(node, val) {
// Update height
updateHeight(node);
const balanceFactor = getBalanceFactor(node);
// Left-Left case
if (balanceFactor > 1 && val < node.left.val) {
return rotateRight(node);
}
// Right-Right case
if (balanceFactor < -1 && val > node.right.val) {
return rotateLeft(node);
}
// Left-Right case
if (balanceFactor > 1 && val > node.left.val) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
// Right-Left case
if (balanceFactor < -1 && val < node.right.val) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}Deletion in Balanced Tree
function deleteNode(root, val) {
// Standard BST deletion
if (root === null) return null;
if (val < root.val) {
root.left = deleteNode(root.left, val);
} else if (val > root.val) {
root.right = deleteNode(root.right, val);
} else {
// Node to be deleted found
if (root.left === null) return root.right;
if (root.right === null) return root.left;
// Node with two children
const successor = findMin(root.right);
root.val = successor.val;
root.right = deleteNode(root.right, successor.val);
}
// Rebalance after deletion
return rebalance(root);
}Time and Space Complexity
| Operation | Time Complexity | Space Complexity |
|-----------|---------------|------------------|
| Check Balance | O(n) | O(h) |
| Insertion (Balanced) | O(log n) | O(h) |
| Deletion (Balanced) | O(log n) | O(h) |
| Search (Balanced) | O(log n) | O(h) |
Where:
- n = number of nodes in tree
- h = height of tree (recursion stack space)
Common Variations
1. Height-Balanced Tree
function isHeightBalanced(root) {
function getHeight(node) {
if (node === null) return 0;
const leftHeight = getHeight(node.left);
const rightHeight = getHeight(node.right);
return 1 + Math.max(leftHeight, rightHeight);
}
function checkBalance(node) {
if (node === null) return true;
const leftHeight = getHeight(node.left);
const rightHeight = getHeight(node.right);
const balanceFactor = Math.abs(leftHeight - rightHeight);
return balanceFactor <= 1 &&
checkBalance(node.left) &&
checkBalance(node.right);
}
return checkBalance(root);
}2. Self-Balancing AVL Tree
class AVLTree {
constructor() {
this.root = null;
}
insert(val) {
this.root = this._insert(this.root, val);
}
_insert(node, val) {
// Standard BST insertion
if (node === null) return new AVLNode(val);
if (val < node.val) {
node.left = this._insert(node.left, val);
} else if (val > node.val) {
node.right = this._insert(node.right, val);
} else {
return node; // Duplicate value
}
// Update height
this.updateHeight(node);
// Get balance factor
const balanceFactor = this.getBalanceFactor(node);
// Left-Left case
if (balanceFactor > 1 && val < node.left.val) {
return this.rotateRight(node);
}
// Right-Right case
if (balanceFactor < -1 && val > node.right.val) {
return this.rotateLeft(node);
}
// Left-Right case
if (balanceFactor > 1 && val > node.left.val) {
node.left = this.rotateLeft(node.left);
return this.rotateRight(node);
}
// Right-Left case
if (balanceFactor < -1 && val < node.right.val) {
node.right = this.rotateRight(node.right);
return this.rotateLeft(node);
}
return node;
}
getBalanceFactor(node) {
if (node === null) return 0;
return this.getHeight(node.left) - this.getHeight(node.right);
}
getHeight(node) {
if (node === null) return 0;
return node.height;
}
updateHeight(node) {
if (node !== null) {
node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
}
}
}Common Mistakes to Avoid
1. Incorrect Balance Factor Calculation
// ❌ Wrong - Not calculating properly
function wrongBalanceFactor(node) {
if (node === null) return 0;
// Wrong order - should be left height - right height
return getHeight(node.right) - getHeight(node.left);
}2. Missing Null Checks
// ❌ Wrong - Not handling edge cases properly
function incompleteBalanceCheck(node) {
const leftHeight = getHeight(node.left);
const rightHeight = getHeight(node.right);
// Missing check for null nodes
return Math.abs(leftHeight - rightHeight) <= 1;
}3. Inefficient Height Calculation
// ❌ Wrong - O(n) calculation for each node
function inefficientBalance(root) {
function calculateHeight(node) {
if (node === null) return 0;
return 1 + Math.max(calculateHeight(node.left), calculateHeight(node.right));
}
// This recalculates height every time - inefficient
return calculateHeight(root) <= 1;
}Comparison with Unbalanced Trees
| Aspect | Balanced Tree | Unbalanced Tree |
|--------|---------------|---------------|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Space | O(n) | O(n) |
| Performance | Consistent | Variable |
Real-World Applications
1. Database Indexing
// Example of maintaining balanced tree for database indexing
class BalancedIndex {
constructor() {
this.tree = new AVLTree();
}
insert(key, value) {
this.tree.insert(key, value);
// Tree automatically maintains balance
}
search(key) {
return this.tree.search(key);
}
}2. File System Organization
// Tree structure for hierarchical file system organization
class FileSystemTree {
constructor() {
this.root = null;
}
// Maintain balance for efficient navigation
addDirectory(path) {
this.root = this.balanceTree(this.root, path);
}
isBalanced() {
return isBalanced(this.root);
}
}3. Expression Evaluation
// Balanced tree for expression parsing and evaluation
class ExpressionTree {
constructor() {
this.root = null;
}
buildExpressionTree(expression) {
// Build balanced tree for optimal evaluation
this.root = this.buildBalancedTree(expression);
}
evaluate() {
return this.evaluateBalanced(this.root);
}
}Performance Optimization Tips
1. Pre-calculate Heights
function optimizedBalanceCheck(node) {
// Store heights to avoid recomputation
if (node === null) return true;
const leftHeight = node.left ? node.left.height : 0;
const rightHeight = node.right ? node.right.height : 0;
return Math.abs(leftHeight - rightHeight) <= 1;
}2. Early Termination
function earlyTerminationCheck(node) {
if (node === null) return true;
// Check balance factor early
const balanceFactor = getBalanceFactor(node);
if (Math.abs(balanceFactor) > 1) return false;
// Continue checking only if needed
return isBalanced(node.left) && isBalanced(node.right);
}Common Interview Questions
1. Validate Balanced Binary Tree
function isBalanced(root) {
function checkBalance(node) {
if (node === null) return 0;
const left = checkBalance(node.left);
if (left === -1) return -1;
const right = checkBalance(node.right);
if (right === -1) return -1;
const diff = Math.abs(left - right);
if (diff > 1) return -1;
return 1 + Math.max(left, right);
}
return checkBalance(root) !== -1;
}2. Find Maximum Balance Factor
function maxBalanceFactor(root) {
let maxFactor = 0;
function calculate(node) {
if (node === null) return 0;
const leftHeight = calculate(node.left);
const rightHeight = calculate(node.right);
const currentFactor = Math.abs(leftHeight - rightHeight);
maxFactor = Math.max(maxFactor, currentFactor);
return 1 + Math.max(leftHeight, rightHeight);
}
calculate(root);
return maxFactor;
}Best Practices
1. Consistent Height Tracking
Always maintain height information for efficient balance checking.
2. Proper Rotation Handling
Implement rotation methods correctly to maintain tree properties.
3. Edge Case Coverage
Handle empty trees, single nodes, and boundary conditions properly.
4. Performance Monitoring
Monitor actual balance factors to understand tree behavior in real applications.
Key Takeaways
- Balance is Critical: Maintains O(log n) performance for all operations
- Self-Maintenance: Balanced trees automatically rebalance during insertions/deletions
- Real-World Impact: Essential for database systems, file systems, and search engines
- Algorithm Foundation: Forms basis for many advanced data structures like B-trees and Red-Black trees
Balanced binary trees are fundamental to efficient data structure design, ensuring consistent performance characteristics regardless of input order or distribution.