Balanced Binary Tree

A binary tree is considered height-balanced if the difference in the heights of its left and right subtrees is no more than 1 for every node in the tree.

Here’s how we can determine if a given binary tree is height-balanced:

  1. Calculate the Height: We’ll define a helper function to calculate the height of a given subtree. The height of a subtree is the number of nodes along the longest path from the root node down to the farthest leaf node.

  2. Check Balance: For each node, we’ll calculate the height of its left and right subtrees. If the difference in heights is greater than 1, we’ll return False.

  3. Recursive Calls: We’ll recursively apply this process to every node in the tree.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(node):
            if not node:
                return 0
            left_height = height(node.left)
            right_height = height(node.right)

            # If left or right subtree is unbalanced, propagate -1 up to the root
            if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
                return -1

            return max(left_height, right_height) + 1

        return height(root) != -1

Key Insights:

  • The helper function calculates the height of a subtree and simultaneously checks if the subtree is balanced.
  • If any subtree is found to be unbalanced, we propagate a value of -1 up to the root to signify that the entire tree is unbalanced.
  • The time complexity of this approach is (O(n)), where (n) is the number of nodes in the tree, and the space complexity is (O(\log n)), assuming a balanced tree, due to the recursion stack.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Boolean}

def height(root)
  if root.nil? 
    return 0
  end
  
  left_height = height(root.left)
  right_height = height(root.right)
  
  return 1 + [left_height, right_height].max
end

def is_balanced(root)
  if root.nil?
    return true
  end
  
  left_height = height(root.left)
  right_height = height(root.right)
  
    if (left_height - right_height).abs > 1
        return false
    else
        return is_balanced(root.left) && is_balanced(root.right)
    end
end

Identifying Problem Isomorphism

“Balanced Binary Tree” is about determining whether a binary tree is height-balanced. In this context, a height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

A simpler problem related to binary tree properties is “Maximum Depth of Binary Tree”. This problem only requires calculating the maximum depth or height of a binary tree. Understanding how to traverse a binary tree and calculate its depth is a prerequisite for determining whether a binary tree is balanced or not.

An approximately isomorphic problem is “Diameter of Binary Tree”. While this problem isn’t about checking if a tree is balanced, it does involve calculating the maximum depth of left and right subtrees for each node, which is similar to what you’d do to check if a tree is balanced.

A more complex isomorphic problem is “Binary Tree Zigzag Level Order Traversal”. This problem is about tree traversal rather than tree balance, but it requires a more intricate traversal algorithm than the simple depth-first search used in the other problems.

From simplest to more complex:

  1. “Maximum Depth of Binary Tree” - Calculate the maximum depth of a binary tree.
  2. “Balanced Binary Tree” - Determine if a binary tree is height-balanced.
  3. “Diameter of Binary Tree” - Determine the diameter (maximum distance between any two nodes) of a binary tree.
  4. “Binary Tree Zigzag Level Order Traversal” - Traverse a binary tree in a zigzag level order pattern.

“Balanced Binary Tree” tests your understanding of binary trees and the concept of balance in binary trees. If you are new to tree-based problems, here are a few problems to build up your understanding of binary trees:

  1. “104. Maximum Depth of Binary Tree”: This problem helps you understand tree traversal and depth calculation in a tree. It’s a simple introduction to the concept of tree depth.

  2. “100. Same Tree”: This problem is another good introduction to the concept of tree traversal and can help you understand how to compare the structures of two trees.

  3. “101. Symmetric Tree”: This problem can help you understand tree symmetry and how to traverse a tree to check for this property.

  4. “108. Convert Sorted Array to Binary Search Tree”: This problem is a bit more challenging and introduces the concept of a binary search tree. It asks you to convert a sorted array into a binary search tree, which is a type of tree that maintains a certain order property.

  5. “111. Minimum Depth of Binary Tree”: This problem helps you understand the concept of depth in a binary tree, which is crucial for understanding the balance in binary trees.

  6. “112. Path Sum”: This problem asks you to find a path in a tree with a certain sum, introducing the concept of a path in a tree.

  7. “226. Invert Binary Tree”: This problem can help you practice tree manipulation techniques and understand the structure of a binary tree better.

  8. “257. Binary Tree Paths”: This problem requires you to list all paths from the root to the leaves of a binary tree, giving you practice with both tree traversal and path construction.

  9. “270. Closest Binary Search Tree Value”: This problem can help you understand the properties of a binary search tree better and how to navigate it.

  10. “235. Lowest Common Ancestor of a Binary Search Tree”: This problem introduces the concept of the lowest common ancestor, which is a common problem in tree-based questions.

These cover how to navigate, manipulate, and analyze binary trees, which should help you tackle the “Balanced Binary Tree” problem more effectively.

1
2
3
4
5
6
7
8

class Solution(object):
    def isBalanced(self, root):
        return (self.Height(root) >= 0)
    def Height(self, root):
        if root is None:  return 0
        leftheight, rightheight = self.Height(root.left), self.Height(root.right)
        if leftheight < 0 or rightheight < 0 or abs(leftheight - rightheight) > 1:  return -1
        return max(leftheight, rightheight) + 1

Problem Classification

This problem can be classified based on the terminology used in the problem statement as follows:

  1. Binary Trees: The problem revolves around a binary tree data structure. A binary tree is a tree-type non-linear data structure with a maximum of two children for each parent.

  2. Tree Height: The problem requires understanding of the concept of tree height, which is the length of the longest path from the root to a leaf.

  3. Balanced Trees: The problem involves determining whether a binary tree is balanced. In this context, a balanced binary tree is one in which the height of the two subtrees of every node never differ by more than 1.

  4. Recursion: The problem requires knowledge of recursion, a common strategy used in tree traversal, where a function calls itself to solve smaller instances of the same problem.

Clarification Questions

What are the clarification questions we can ask about this problem?

Identifying Problem Isomorphism

The problem “110. Balanced Binary Tree” requires checking if a binary tree is height-balanced.

A closely related problem is “104. Maximum Depth of Binary Tree”. In this problem, you’re asked to find the maximum depth of a binary tree.

Both problems are related to the height of a binary tree. While the first problem asks if the tree is balanced (meaning the depths of two subtrees of every node never differ by more than 1), the second problem asks for the maximum depth of the tree.

Understanding the maximum depth of a binary tree is a critical component in determining if a binary tree is balanced, as it involves calculating the height of the tree from its root to the farthest leaf node. Therefore, “104. Maximum Depth of Binary Tree” can be considered an approximate isomorphic problem to “110. Balanced Binary Tree”.

Which problem does this problem map to the corresponding isomorphic problem on Leetcode ?

Visual Model of the Problem

To visualize the “Balanced Binary Tree” problem, you’ll want to draw out a binary tree, which is a type of tree where each node has at most two children, referred to as the left child and the right child.

A binary tree is said to be “balanced” if for each node in the tree, the height (number of layers) of its left subtree and the height of its right subtree differ by no more than 1.

Here’s a visualization of a balanced binary tree:

      A
     / \
    B   C
   / \   \
  D   E   F

In this tree, every node (A, B, C, D, E, F) has a left and right subtree height difference of no more than 1, so it’s a balanced tree.

Here’s an example of an unbalanced binary tree:

      A
     / 
    B   
   /  
  C   
 /
D

In this case, Node A has a left subtree height of 3 (B, C, D) and a right subtree height of 0 (no right subtree), so the difference is 3 which is more than 1. Hence, the tree is unbalanced.

This visualization helps in understanding the condition for a balanced binary tree and gives a way to approach the problem by comparing the heights of left and right subtrees for every node.

Language Agnostic Coding Drills

  1. Understanding Binary Trees: This problem involves binary trees. Understanding how they work is the first key step.

  2. Recursive Functions: The solution involves recursion, as it dives deeper into each level of the tree.

  3. Tree Height: This problem involves determining the height of a tree, which is the longest path from the root to a leaf.

  4. Balanced Trees: A balanced binary tree is one where the depth of all the leaves differs by at most one.

Targeted Drills in Python

  1. Understanding Binary Trees:
1
2
3
4
5

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
  1. Recursive Functions:
1
2
3
4
5
6
7

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # prints 120
  1. Tree Height:
1
2
3
4
5
6
7
8

class Solution:
    def maxDepth(self, root):
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1
  1. Balanced Trees:

This is where we introduce the concept of balanced trees. We can make an adjustment to our maxDepth function above to determine whether a tree is balanced:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def isBalanced(self, root):
        if root is None: 
            return True
        left_height = self.maxDepth(root.left) 
        right_height = self.maxDepth(root.right) 
        return abs(left_height - right_height) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
        
    def maxDepth(self, root):
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1

These drills incorporate the necessary concepts for this problem. We start by understanding the basics of binary trees, and then move on to recursion, which is a key concept for most tree problems. Then we introduce the concept of tree height, which is needed to check whether a tree is balanced or not. Finally, we introduce the concept of a balanced tree itself.