Balanced Binary Tree easy

Problem Statement

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than one.

Example 1

Input: root = [3,9,20,null,null,15,7] Output: true

Example 2

Input: root = [1,2,2,3,3,null,null,4,4] Output: false

Steps

1. Recursive Depth Calculation: We'll use a recursive helper function to calculate the height of each subtree. This function will also check for balance at each node.

2. Height Check: The helper function will return the height of the subtree if it's balanced. If it's unbalanced, it will return -1 to signal an imbalance.

3. Base Case: An empty tree (null node) has a height of 0.

4. Recursive Step: For a non-empty node:

   • Recursively calculate the height of the left and right subtrees.
   • If either subtree is unbalanced (returns -1), the current node's subtree is also unbalanced, so return -1.
   • If the absolute difference between the left and right subtree heights is greater than 1, the current node's subtree is unbalanced, so return -1.
   • Otherwise, the current node's subtree is balanced, return the maximum of the left and right subtree heights plus 1 (for the current node).

5. Main Function: The main function simply calls the recursive helper function with the root node. If the helper function returns a non-negative value, the tree is balanced; otherwise, it's not.

Explanation

The solution uses a post-order traversal approach. We recursively check the balance of the left and right subtrees before determining the balance of the current node. This ensures that we check all subtrees before making a determination about the overall balance of the tree. The use of -1 as a signal for imbalance simplifies the logic and avoids the need for separate boolean variables to track balance status.

Code

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public bool IsBalanced(TreeNode root) {
        return CheckHeight(root) != -1;
    }

    private int CheckHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = CheckHeight(node.left);
        if (leftHeight == -1) {
            return -1;
        }

        int rightHeight = CheckHeight(node.right);
        if (rightHeight == -1) {
            return -1;
        }

        if (Math.Abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        return Math.Max(leftHeight, rightHeight) + 1;
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be N, but in a balanced tree, H is log N.