Balanced Binary Tree Checker

Balanced Binary Tree Checker

January 1, 2024
medium
DFS

Problem #

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

Example: #

Consider the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Output: True Explanation: This binary tree is balanced as the heights of the left and right subtrees of every node differ by no more than 1.

Solution: #

Approach: Depth-First Search (DFS) #

The solution involves performing a depth-first search (DFS) on the tree. During the DFS, we calculate the height of each subtree. If the difference in heights of any two subtrees is more than one, we can immediately conclude that the tree is not balanced.

Algorithm Steps: #

  1. Define a helper function checkHeight that computes the height of a tree rooted at a given node and determines if it’s balanced.
  2. In checkHeight, if the node is null, return a height of 0, indicating the tree is trivially balanced.
  3. Recursively check the height of the left and right children.
  4. If the left or right subtree is unbalanced, or if the height difference between the left and right subtree is greater than 1, return an error code (e.g., -1).
  5. Otherwise, return the height of the current node, which is 1 plus the height of its taller child.
  6. The tree is balanced if the checkHeight function does not return the error code for the root node.

Code in Python: # 

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

def isBalanced(root):
    def checkHeight(node):
        if not node:
            return 0
        
        leftHeight = checkHeight(node.left)
        if leftHeight == -1:
            return -1
        
        rightHeight = checkHeight(node.right)
        if rightHeight == -1:
            return -1
        
        if abs(leftHeight - rightHeight) > 1:
            return -1
        else:
            return max(leftHeight, rightHeight) + 1

    return checkHeight(root) != -1

Time Complexity: #

  • O(n), where n is the number of nodes in the tree. We visit each node once.

Space Complexity: #

  • O(n) in the worst case (for a skewed tree), or O(log n) for a balanced tree, due to recursion.

This problem is a great example of using DFS in a binary tree to check for certain properties, in this case, the balance of the tree. It demonstrates the efficiency and elegance of recursion in tree-based algorithms.