Let’s break down the problem of checking if a Binary Search Tree (BST) is balanced, and then we’ll go through the steps to solve it along with code examples in multiple programming languages.
What is a Balanced Binary Search Tree?
A binary search tree (BST) is considered balanced if the depth (or height) of the two subtrees of every node differ by no more than 1. This property ensures that the tree remains relatively flat, which helps in keeping operations like search, insertion, and deletion efficient.
Example of a Balanced BST
Consider the following BST:
4
/ \
2 6
/ \ / \
1 3 5 7In this tree:
- The left subtree of node 4 (root) has a height difference of 0 with the right subtree.
- Similarly, all subtrees within this BST satisfy the balanced property.
Example of an Unbalanced BST
Consider this tree:
4
/
2
/
1In this tree:
- The left subtree of node 4 has a height difference of 2 with the right subtree (which is empty).
- This tree is unbalanced because the height difference is greater than 1.
Approach to Check if a BST is Balanced
- Height Calculation: Calculate the height of each subtree.
- Check Balance: For each node, check if the height difference between the left and right subtree is at most 1.
Steps in Detail
- Compute Height and Check Balance:
- For each node, compute the height of its left and right subtrees.
- The height of a node is the maximum height of its subtrees plus one.
- If the height difference between left and right subtree is more than 1 at any node, the tree is unbalanced.
- Recursive Approach: Use recursion to traverse the tree and check balance for each node.
To check if a binary search tree (BST) is balanced, you need to ensure that the difference in heights between the left and right subtrees of any node is no more than one. A balanced BST maintains this property for all nodes. Here’s a simple function to determine if a BST is balanced, implemented in Python:
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def is_balanced(root):
"""
Check if the binary search tree (BST) is balanced.
:param root: TreeNode, the root of the binary search tree
:return: True if the tree is balanced, False otherwise
"""
def check_height(node):
"""
Helper function to check the height of the node and balance status.
:param node: TreeNode, the node to check
:return: A tuple (is_balanced, height) where:
- is_balanced is True if the subtree rooted at node is balanced, False otherwise
- height is the height of the subtree rooted at node
"""
if not node:
return True, 0
left_balanced, left_height = check_height(node.left)
right_balanced, right_height = check_height(node.right)
# The current node is balanced if the left and right subtrees are balanced
# and the difference in heights is no more than 1
current_balanced = (left_balanced and right_balanced and abs(left_height - right_height) <= 1)
# Height of the current node is the maximum height of its subtrees plus 1
current_height = max(left_height, right_height) + 1
return current_balanced, current_height
balanced, _ = check_height(root)
return balancedExplanation:
- TreeNode Class: Defines a node in the binary tree with a value and pointers to left and right children.
- is_balanced Function: This is the main function that determines if the BST is balanced. It uses a helper function
check_heightto compute the balance status and height of each subtree. - check_height Function:
- If the node is
None(base case), the subtree is considered balanced with a height of0. - Recursively check the height and balance status of the left and right subtrees.
- The subtree is balanced if both subtrees are balanced and the height difference is within the allowed limit (<= 1).
- Compute the height of the current subtree as the maximum height of its left or right subtree plus
1.
- If the node is
This approach ensures that the function runs in O(n) time complexity, where n is the number of nodes in the tree, as each node is visited once.
Code Examples
Python
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def is_balanced(root):
def check_height(node):
if not node:
return 0
left_height = check_height(node.left)
right_height = check_height(node.right)
if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
return -1
return max(left_height, right_height) + 1
return check_height(root) != -1Java
class TreeNode {
int value;
TreeNode left, right;
TreeNode(int value) {
this.value = value;
this.left = this.right = null;
}
}
public class BalancedBST {
public static boolean isBalanced(TreeNode root) {
return checkHeight(root) != -1;
}
private static int checkHeight(TreeNode node) {
if (node == null) return 0;
int leftHeight = checkHeight(node.left);
int rightHeight = checkHeight(node.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
}C++
#include <algorithm>
#include <cmath>
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
bool isBalanced(TreeNode* root) {
return checkHeight(root) != -1;
}
private:
int checkHeight(TreeNode* node) {
if (!node) return 0;
int leftHeight = checkHeight(node->left);
int rightHeight = checkHeight(node->right);
if (leftHeight == -1 || rightHeight == -1 || std::abs(leftHeight - rightHeight) > 1) {
return -1;
}
return std::max(leftHeight, rightHeight) + 1;
}
};Explanation
checkHeightFunction: Computes the height of each subtree. If at any point, the height difference between subtrees is more than 1, it returns -1 to indicate that the tree is unbalanced.is_balancedFunction: Callscheck_heightand checks if it returned -1.
This approach ensures that each node is visited once, making the time complexity O(n), where n is the number of nodes in the tree.
