Leetcode – Balanced Binary Tree in Python

Introduction

Balanced Binary Tree is a classic problem in data structures and algorithms and is quite popular on coding challenge platforms such as LeetCode. It tests your ability to work with trees, particularly binary trees, and assess their properties. In this comprehensive article, we’ll take an in-depth look at the problem, understand the underlying concepts of balanced binary trees, and go through various methods to solve the problem in Python.

Understanding the Problem

The Balanced Binary Tree problem on LeetCode asks to determine if a binary tree is height-balanced. 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 1.

The Binary Tree Data Structure

Before diving into the problem, let’s quickly recap what a binary tree is. A binary tree is a hierarchical data structure in which each node has at most two children, typically referred to as the left child and the right child.

A binary tree node can be represented in Python as follows:

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

The Concept of a Balanced Binary Tree

A balanced binary tree is a binary tree with an added constraint on the heights of its subtrees. For each node in the tree, the height of its left subtree and the height of its right subtree should not differ by more than 1. Height is the number of edges on the longest path from a node to a leaf.

Approaches to Solving the Problem

Now, let’s go through various approaches to solve the Balanced Binary Tree problem.

Approach 1: Brute Force Approach

In the brute force approach, we can recursively check for each node if the left subtree is balanced, the right subtree is balanced, and the difference in heights of left and right subtrees is not more than 1.

Let’s look at the Python code for this approach:

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

def isBalanced(root):
    def height(node):
        if not node:
            return 0
        return 1 + max(height(node.left), height(node.right))

    if not root:
        return True

    left_height = height(root.left)
    right_height = height(root.right)

    return abs(left_height - right_height) <= 1 and isBalanced(root.left) and isBalanced(root.right)

# Example usage:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(isBalanced(root))  # Output: True

This approach has a time complexity of O(n^2) for a skewed tree, which is not efficient for large datasets.

Approach 2: Optimized Recursive Approach

We can optimize the previous approach by avoiding repeated calculations. Instead of calculating the height separately, we can calculate the height in the same recursion where we check if a subtree is balanced. If we find that a subtree is not balanced, we can return early without checking the entire tree.

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

def isBalanced(root):
    def check_balance(node):
        if not node:
            return 0
        
        left_height = check_balance(node.left)
        if left_height == -1:
            return -1
        
        right_height = check_balance(node.right)
        if right_height == -1:
            return -1
        
        if abs(left_height - right_height) > 1:
            return -1
        
        return 1 + max(left_height, right_height)
    
    return check_balance(root) != -1

# Example usage:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(isBalanced(root))  # Output: True

This optimized approach has a time complexity of O(n), making it much faster than the brute force approach.

Analyzing the Problem’s Constraints

It’s important to understand the constraints of the problem. For example, what is the maximum number of nodes in the binary tree? This can affect which solution is viable.

Further Optimizations and Variations

While the optimized recursive approach is generally efficient, in certain cases involving extremely deep recursion, it could cause a stack overflow. You might consider using an iterative approach using a stack to avoid this problem.

Additionally, you can experiment with different ways of representing the binary tree, like using an array-based representation, which might have cache advantages.

Conclusion

In this article, we delved into the Balanced Binary Tree problem on LeetCode. We explored what binary trees are, the concept of balanced binary trees, and different approaches to solving the problem in Python. Understanding the underlying concepts and choosing the right algorithm is key to efficiently solving this problem. Practice implementing these approaches to deepen your understanding of binary trees and their applications.