Balanced Binary Tree

class Solution {
private:
    // Determines if a binary tree is height-balanced and records the height
    bool checkBalance(TreeNode* node, int& height) {
        if (!node) {
            height = -1;
            return true;
        }

        int leftHeight, rightHeight;
        if (checkBalance(node->left, leftHeight) && checkBalance(node->right, rightHeight) && abs(leftHeight - rightHeight) < 2) {
            height = 1 + max(leftHeight, rightHeight);
            return true;
        }
        return false;
    }

public:
    bool isBalanced(TreeNode* root) {
        int treeHeight;
        return checkBalance(root, treeHeight);
    }
};

This C++ solution implements a function to determine if a binary tree is balanced. A binary tree is balanced if, for every node, the height difference between its left and right subtree is at most 1. The solution uses a helper function, checkBalance, which recursively verifies the balance condition and calculates the height of the tree simultaneously.

Understand the structure and flow of the code with these key points:

• The function checkBalance takes a TreeNode* and a reference to an integer height. The integer height stores the height of the subtree for which the node acts as the root.
• If the current node pointer is null, indicating a leaf node's child, it sets the height to -1 and returns true, as a null node is trivially balanced.
• Two integers, leftHeight and rightHeight, keep track of the heights of the left and right subtrees, respectively.
• Recursive calls are made to check the balance of left and right children. If both subtrees are balanced and the difference in their heights is less than two, then it updates the node's height and returns true, indicating that the subtree rooted at this node is balanced.
• If the conditions fail, checkBalance returns false, indicating an imbalance.
• The isBalanced function is the primary function that the users call. It begins the recursive checking process from the root node.

The technique used here effectively reduces the need to traverse any part of the tree more than once, thus ensuring a time-efficient solution.

// Helper class to manage attributes of recursive tree processing
final class NodeInfo {
    public final int nodeHeight;
    public final boolean isTreeBalanced;

    public NodeInfo(int height, boolean balanced) {
        this.nodeHeight = height;
        this.isTreeBalanced = balanced;
    }
}

class Solution {
    // Recursively check if tree rooted at node is balanced, capturing height
    private NodeInfo checkBalance(TreeNode node) {
        // Base case: An empty tree is inherently balanced, height = -1
        if (node == null) {
            return new NodeInfo(-1, true);
        }

        // Recursive check on the left subtree
        NodeInfo leftSubtree = checkBalance(node.left);
        if (!leftSubtree.isTreeBalanced) {
            return new NodeInfo(-1, false);
        }
        // Recursive check on the right subtree
        NodeInfo rightSubtree = checkBalance(node.right);
        if (!rightSubtree.isTreeBalanced) {
            return new NodeInfo(-1, false);
        }

        // Determine current node balance from child nodes' heights
        if (Math.abs(leftSubtree.nodeHeight - rightSubtree.nodeHeight) < 2) {
            return new NodeInfo(Math.max(leftSubtree.nodeHeight, rightSubtree.nodeHeight) + 1, true);
        }
        return new NodeInfo(-1, false);
    }

    public boolean isBalanced(TreeNode node) {
        return checkBalance(node).isTreeBalanced;
    }
}

This program in Java determines if a binary tree is balanced. A balanced tree is where, for each node, the heights of the left and right subtrees differ by no more than one.

The program is organized into two classes:

• NodeInfo: A helper class that contains the height of the node and a boolean indicating if the subtree rooted at this node is balanced.
• Solution: Contains methods to assess the balance of the tree.

Process and Key Elements:

1. The checkBalance method recursively checks if a tree rooted at a given node is balanced and calculates its height.

   • It begins by handling the base case where the node is null. A null node is considered balanced and given a height of -1.
   • The method then recursively checks the left and right subtrees for balance using the same checkBalance method.
   • After receiving information from both subtrees, it calculates the height difference.
   • If the height difference is less than 2 and both subtrees are balanced, the current node is also considered balanced, and its height is set as one plus the maximum of the heights of both subtrees.
   • If any subtree is unbalanced or the height difference condition fails, the current node is deemed unbalanced.

2. The isBalanced public method starts the recursive checking process for the tree from the root node and returns the balance status.

Key output constraints:

• Return the result directly from the isBalanced method, which utilizes the helper class for maintaining the state during recursion.

This structure efficiently determines tree balance by reducing redundant checks, using post-order traversal to assess balance from the bottom up, allowing immediate termination if any subtree is unbalanced.

typedef struct {
    int depth;
    bool isStable;
} BalanceStatus;

BalanceStatus checkBalance(struct TreeNode* node) {
    BalanceStatus status;
    if (node == NULL) {
        status.depth = -1;
        status.isStable = true;
        return status;
    }
    
    BalanceStatus leftStatus = checkBalance(node->left);
    if (!leftStatus.isStable) {
        status.depth = -1;
        status.isStable = false;
        return status;
    }
    
    BalanceStatus rightStatus = checkBalance(node->right);
    if (!rightStatus.isStable) {
        status.depth = -1;
        status.isStable = false;
        return status;
    }
    
    if (abs(leftStatus.depth - rightStatus.depth) < 2) {
        status.depth = (leftStatus.depth > rightStatus.depth ? leftStatus.depth : rightStatus.depth) + 1;
        status.isStable = true;
        return status;
    }
    
    status.depth = -1;
    status.isStable = false;
    return status;
}

bool isTreeBalanced(struct TreeNode* node) {
    return checkBalance(node).isStable;
}

In this solution, you determine if a binary tree is balanced by checking the height difference of left and right subtrees at each node.

• The BalanceStatus structure contains:
  • depth - the depth of the subtree rooted at the node.
  • isStable - a boolean that determines if the subtree is balanced.

The checkBalance function recurses through the binary tree:

1. Base case: If the current node is NULL, it returns a depth of -1 and isStable as true, indicating an empty subtree is balanced.
2. Recursive case:
   • Calculate leftStatus for the left subtree and rightStatus for the right subtree.
   • If either subtree is unbalanced (isStable is false), the current subtree is marked as unbalanced.
   • If the subtrees differ in depth by less than 2 and both are stable, update the current depth and set isStable to true.
   • If the condition is not met, the current subtree is marked unbalanced.

The isTreeBalanced function simply checks if the root node's subtree (the entire tree) is stable using the checkBalance function.

This approach efficiently verifies the tree's balance by checking all nodes just once through recursive depth-first traversal, with a time complexity of O(n).

// Class to encapsulate tree attributes
class TreeStatus {
    constructor(nodeHeight, isBalanced) {
        this.nodeHeight = nodeHeight;
        this.isBalanced = isBalanced;
    }
}

var checkBalanced = function(node) {
    // Helper function to check if the tree with given node is balanced
    function helper(node) {
        // Base case: Null node indicates a balanced tree
        if (node === null) {
            return new TreeStatus(-1, true);
        }

        // Recursively check left subtree
        const leftStatus = helper(node.left);
        if (!leftStatus.isBalanced) {
            return new TreeStatus(-1, false);
        }

        // Recursively check right subtree
        const rightStatus = helper(node.right);
        if (!rightStatus.isBalanced) {
            return new TreeStatus(-1, false);
        }

        // Compare heights of left and right subtrees
        if (Math.abs(leftStatus.nodeHeight - rightStatus.nodeHeight) < 2) {
            // If the current node is balanced, calculate height and return balanced status
            return new TreeStatus(Math.max(leftStatus.nodeHeight, rightStatus.nodeHeight) + 1, true);
        }
        return new TreeStatus(-1, false);
    }
    // Initiate helper function from root and return the balanced status
    return helper(node).isBalanced;
};

The JavaScript solution provided tackles the problem of determining whether a binary tree is balanced. In this context, a balanced binary tree is defined where the height difference between the left and right subtree of any node is no more than 1.

• The implementation defines a helper class TreeStatus that tracks two properties:

  • nodeHeight: the height of the node within the tree.
  • isBalanced: a boolean that indicates whether the subtree rooted at this node is balanced.

• The main function, checkBalanced, uses a recursive helper function to traverse the tree:

  1. It begins at the root and explores each node, checking for balance as it progresses.
  2. For each node, it first recursively checks the left child.
  3. If the left subtree is unbalanced, the function immediately returns a TreeStatus indicating the tree is not balanced.
  4. Similar checks are performed for the right subtree.
  5. If both child subtrees are balanced, the function then checks the height difference between them.
  6. If the difference is less than or equal to 1, the node is considered balanced and it calculates the current node height.
  7. If at any node the subtree height difference is greater than 1, the function deems the tree unbalanced and terminates further checks.
  8. After traversing the whole tree, the balance status of the root is returned, which effectively represents the status of the entire tree.

This approach is efficient as it minimizes the number of checks using early exits when an imbalance is detected, ensuring optimal performance in scenarios with large data structures.

class Solution:
    def checkBalance(self, node: TreeNode) -> (bool, int):
        if not node:
            return True, -1
        
        left_balanced, left_depth = self.checkBalance(node.left)
        if not left_balanced:
            return False, 0
        right_balanced, right_depth = self.checkBalance(node.right)
        if not right_balanced:
            return False, 0
        
        is_balanced = abs(left_depth - right_depth) < 2
        depth = 1 + max(left_depth, right_depth)
        return is_balanced, depth

    def treeIsBalanced(self, node: TreeNode) -> bool:
        return self.checkBalance(node)[0]

The Python solution provided is designed to check if a binary tree is balanced. A balanced binary tree is one where the height difference between the left and right subtrees of any node is not more than one, and this must apply recursively across all nodes in the tree.

The solution features a Solution class equipped with two methods:

• checkBalance method:

  • Accepts a node as input, indicating a single node of the binary tree.
  • Returns a tuple consisting of a boolean and an integer. The boolean indicates whether the subtree rooted at the node is balanced while the integer represents its depth.
  • Begins by checking if the current node is None (base case), returning True and -1 to indicate a balanced subtree with a depth of -1 (since the tree is empty).
  • Recursively calls itself to assess the left and right subtrees, extracting the balanced status and depth for both sides.
  • If either subtree is not balanced, it returns False and 0 immediately.
  • Determines the balance status of the current node by comparing the depths of the left and right subtree; if the difference is less than 2, it remains balanced.
  • Computes the depth of the current tree by taking the maximum of left and right subtree depths and adding one.

• treeIsBalanced method:

  • Receives a node, indicating the root of the binary tree.
  • Utilizes the checkBalance method returning just the boolean value from the tuple, which signifies whether the complete tree is balanced starting from the provided root.

This efficient approach ensures a O(n) time complexity since each node is visited once, and the balance and depth are calculated in a single pass through the tree, making it quite optimal for larger trees.