Efficiently Checking Binary Tree Balance: The -1 Sentinel Pattern

on


Checking the height of a binary tree is essential when we want to determine if it is balanced.

AVL trees are a category of binary search trees that are always balanced to ensure an O(log n) runtime for search, insertion, and deletion operations. When inserting into or deleting from an AVL tree, we must calculate the balance factor of the nodes and rebalance the tree using rotations whenever an imbalance occurs.

During this process, checking whether the tree is balanced in a single pass—rather than recomputing heights repeatedly—is the most efficient way to do it.

We can achieve this by using -1 as a sentinel value for a cleaner, O(n) implementation:

  • Returning -1 indicates that a subtree is already unbalanced.
  • Returning a non-negative integer conveys the actual height of the subtree, which can then be used by parent nodes to calculate their own balance factors.

The Code Implementation

Here is how this single-pass height checking and balance detection logic looks in Python:

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

def check_height(root: TreeNode) -> int:
    """
    Returns the height of the tree if it is balanced.
    Returns -1 if the tree (or any subtree) is unbalanced.
    """
    if not root:
        return 0  # An empty tree has a height of 0 and is balanced
    
    # Check left subtree
    left_height = check_height(root.left)
    if left_height == -1:
        return -1  # Left subtree is not balanced
    
    # Check right subtree
    right_height = check_height(root.right)
    if right_height == -1:
        return -1  # Right subtree is not balanced
    
    # Check if current node is balanced
    if abs(left_height - right_height) > 1:
        return -1  # Current node is not balanced
    
    # Return height of the current subtree
    return 1 + max(left_height, right_height)

def is_balanced(root: TreeNode) -> bool:
    return check_height(root) != -1

Unit Test Suite

Click to expand full unit test suite (unittest)

To ensure our implementation covers all edge cases—such as empty trees, single nodes, balanced trees, and deep imbalances—we can use Python's built-in unittest module:

import unittest

class TestBinaryTreeBalance(unittest.TestCase):

    def test_empty_tree(self):
        """An empty tree should be considered balanced with height 0."""
        self.assertTrue(is_balanced(None))
        self.assertEqual(check_height(None), 0)

    def test_single_node(self):
        """A single-node tree is balanced with height 1."""
        root = TreeNode(1)
        self.assertTrue(is_balanced(root))
        self.assertEqual(check_height(root), 1)

    def test_perfectly_balanced_tree(self):
        """
        Tree structure:
               1
             /   \
            2     3
           / \   / \
          4   5 6   7
        """
        root = TreeNode(1,
            left=TreeNode(2, TreeNode(4), TreeNode(5)),
            right=TreeNode(3, TreeNode(6), TreeNode(7))
        )
        self.assertTrue(is_balanced(root))
        self.assertEqual(check_height(root), 3)

    def test_balanced_with_height_difference_of_one(self):
        """
        Tree structure:
               1
             /   \
            2     3
           /
          4
        """
        root = TreeNode(1,
            left=TreeNode(2, left=TreeNode(4)),
            right=TreeNode(3)
        )
        self.assertTrue(is_balanced(root))
        self.assertEqual(check_height(root), 3)

    def test_unbalanced_left_heavy(self):
        """
        Tree structure (Linked List style):
             1
            /
           2
          /
         3
        """
        root = TreeNode(1, left=TreeNode(2, left=TreeNode(3)))
        self.assertFalse(is_balanced(root))
        self.assertEqual(check_height(root), -1)

    def test_unbalanced_right_heavy(self):
        """
        Tree structure:
          1
           \
            2
             \
              3
        """
        root = TreeNode(1, right=TreeNode(2, right=TreeNode(3)))
        self.assertFalse(is_balanced(root))
        self.assertEqual(check_height(root), -1)

    def test_unbalanced_deep_subtree(self):
        """
        Root appears balanced at top level (both subtrees present), 
        but the left subtree is internally unbalanced.
        
        Tree structure:
                   1
                 /   \
                2     3
               /
              4
             /
            5
        """
        root = TreeNode(1,
            left=TreeNode(2, left=TreeNode(4, left=TreeNode(5))),
            right=TreeNode(3)
        )
        self.assertFalse(is_balanced(root))
        self.assertEqual(check_height(root), -1)

    def test_unbalanced_sub_node_short_circuits(self):
        """
        The imbalance occurs deep inside a subtree, so it returns -1 early.
        
        Tree structure:
                   1
                 /   \
                2     3
               / \
              4   5
             /
            6
           /
          7
        """
        left_sub = TreeNode(2,
            left=TreeNode(4, left=TreeNode(6, left=TreeNode(7))),
            right=TreeNode(5)
        )
        root = TreeNode(1, left=left_sub, right=TreeNode(3))
        self.assertFalse(is_balanced(root))
        self.assertEqual(check_height(root), -1)


if __name__ == '__main__':
    unittest.main()

Key Takeaways

  • Avoid Recomputation: A naive approach calculates height separately for every node, leading to an O(n²) time complexity: To find the height of any given node, you must traverse down all of its descendant nodes to the lowest leaf.
  • Early Termination: By bubbling up -1 as soon as an imbalance is detected, the algorithm short-circuits early without wasting computation on the rest of the tree.
  • Optimal Time Complexity: This sentinel pattern checks balance and computes heights simultaneously in a single bottom-up post-order traversal, keeping time complexity down to O(n).

Comments

Post a Comment