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  7

In 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
  /
 1

In 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

  1. Height Calculation: Calculate the height of each subtree.
  2. Check Balance: For each node, check if the height difference between the left and right subtree is at most 1.

Steps in Detail

  1. 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.
  1. Recursive Approach: Use recursion to traverse the tree and check balance for each node.
See also  How do you sort an array of integers in ascending order?

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 balanced

Explanation:

  1. TreeNode Class: Defines a node in the binary tree with a value and pointers to left and right children.
  2. is_balanced Function: This is the main function that determines if the BST is balanced. It uses a helper function check_height to compute the balance status and height of each subtree.
  3. check_height Function:
    • If the node is None (base case), the subtree is considered balanced with a height of 0.
    • 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.

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.

See also  How do you calculate the number of numerical digits in a string?

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) != -1

Java

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

  • checkHeight Function: 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_balanced Function: Calls check_height and 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.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *