algoadvance

Leetcode 110. Balanced Binary Tree

Problem Statement

Leetcode Problem 110: Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

Example:

  1. Given the following tree [3,9,20,null,null,15,7]:
    3
   / \
  9  20
    /  \
   15   7

Return true.

  1. Given the following tree [1,2,2,3,3,null,null,4,4]:
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Return false.

Clarifying Questions

  1. Input Format:
    • Are the nodes values unique in the binary tree? (It doesn’t matter for this problem)
    • Does the input binary tree include null nodes for missing children? (Yes, as depicted in the examples)
  2. Output Format:
    • Should the function return a boolean value? (True if balanced, False otherwise)

Strategy

To determine if a binary tree is balanced, you need to check the height of each subtree and ensure the difference in height is no more than 1 for any node. A common way to solve this is through a combination of depth-first traversal and height calculation:

  1. Define a helper function height that computes the height of each subtree. If an imbalance is detected, return an error code (e.g., -1).
  2. Use the helper function to check the height from the root of the tree.
  3. In the helper function:
    • If a node is null, return 0 (height of empty subtree).
    • Recursively compute the left and right subtree heights.
    • If either subtree is unbalanced (returns -1), propagate the error code.
    • If the height difference between subtrees is more than 1, return -1 (indicating imbalance).
    • Otherwise, return the height of the current subtree.
  4. The main function checks if the returned value from the helper is -1 (unbalanced) or a positive height (balanced).

Code

#include <iostream>
#include <algorithm>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {}
};

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return checkHeight(root) != -1;
    }

private:
    int checkHeight(TreeNode* node) {
        if (!node) {
            return 0; // A null node is balanced with height 0
        }
        
        int leftHeight = checkHeight(node->left);
        int rightHeight = checkHeight(node->right);
        
        // If the left or right subtree is unbalanced, propagate the failure upwards
        if (leftHeight == -1 || rightHeight == -1) {
            return -1;
        }
        
        // If the height difference is more than 1, mark this node as unbalanced
        if (std::abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        
        // Return the height of the subtree rooted at this node
        return std::max(leftHeight, rightHeight) + 1;
    }
};

Time Complexity

This approach checks both the height and balance of the subtrees efficiently in a single traversal.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI