Balanced Binary Tree: An Algorithmic Challenge

In computer science, understanding the structure of trees is fundamental. One such important property is that a binary tree should be balanced for optimal performance in operations like searching and insertion.

Problem Statement

A binary tree is considered balanced if for every node, the height difference between its left subtree and right subtree is no more than one. This property must hold true for all nodes in the tree.

Algorithmic Approach / Logic

To determine if a binary tree is balanced, we can use a recursive approach:

Calculate the height of each subtree starting from the root.
Check if the absolute difference between the heights of the left and right subtrees is at most one for the current node.
If both conditions are satisfied, the tree rooted at the current node is balanced; otherwise, it is not.

Code Implementation

def height(node):
  if not node:
    return -1
  left = height(node.left)
  right = height(node.right)
  return max(left, right) + 1

def is_balanced(root):
  if not root:
    return True
  left_height = height(root.left)
  right_height = height(root.right)
  return abs(left_height - right_height) <= 1 and is_balanced(root.left) and is_balanced(root.right)

Complexity Analysis

The time complexity of this solution is O(n), where n is the number of nodes in the tree, as we visit each node once. The space complexity is also O(n) due to the recursion stack in the worst case (e.g., a skewed tree).