We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Balanced Binary Tree

Difficulty: Easy

Problem Description

Given a binary tree, determine if it is height-balanced. A binary tree is considered height-balanced if the depth of the two subtrees of every node never differs by more than one.

Key Insights

  • A height-balanced tree must have subtrees that differ in height by at most one.
  • The height of a tree can be calculated recursively.
  • If any subtree is not balanced, the whole tree is not balanced.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, as each node is visited once. Space Complexity: O(h) - where h is the height of the tree, due to the recursive call stack.

Solution

To determine if a binary tree is height-balanced, we can use a depth-first search (DFS) approach. The idea is to recursively check the heights of the left and right subtrees for each node. If at any point the height difference exceeds one, we can immediately conclude that the tree is not balanced.

  1. Define a recursive function that calculates the height of a subtree.
  2. While calculating the height, also check if the subtree is balanced.
  3. If a subtree is found to be unbalanced, propagate that information up the recursive calls.
  4. The root function will return true or false based on whether the entire tree is balanced.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isBalanced(root: TreeNode) -> bool:
    def checkHeight(node):
        if not node:
            return 0  # Height of an empty node is 0

        left_height = checkHeight(node.left)
        if left_height == -1:  # Left subtree is not balanced
            return -1

        right_height = checkHeight(node.right)
        if right_height == -1:  # Right subtree is not balanced
            return -1

        if abs(left_height - right_height) > 1:  # Current node is unbalanced
            return -1

        return max(left_height, right_height) + 1  # Return height of the node

    return checkHeight(root) != -1  # If the result is not -1, the tree is balanced
← Back to All Questions