Understanding Tree Properties — Implementation Guide

1. Calculating Tree Height

The height of a tree is the number of edges on the longest path from root to leaf. An empty tree has height -1 (or 0 if counting nodes).

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

• Time: O(n) — visit each node once
• Space: O(h) — recursion stack depth
• Pattern: Post-order traversal (process children first)

2. Checking if a Tree is Balanced

A balanced tree has |leftHeight - rightHeight| ≤ 1 for every node. The key is combining height calculation with balance checking.

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

The -1 sentinel propagates imbalance upward immediately, enabling early termination.

3. Checking Symmetry

A symmetric tree mirrors itself: left subtree equals right subtree when reversed.

def isSymmetric(root):
    def mirror(left, right):
        if not left and not right: return True
        if not left or not right: return False
        return (left.val == right.val and
                mirror(left.left, right.right) and
                mirror(left.right, right.left))
    return mirror(root.left, root.right) if root else True

Compare left.left with right.right (outer) and left.right with right.left (inner).

4. Common Operations Summary

5. Common Pitfalls

• Calculating height separately: Naive balance check calls height() for each node → O(n²). Combine them!
• Forgetting empty tree: Always handle null/None as base case (height -1 or 0)
• Wrong sentinel value: Use -1 (invalid height) to signal imbalance; valid heights are ≥ 0
• Not propagating -1: If a subtree returns -1, immediately return -1 without more work
• Depth vs Height confusion: Depth is from root to node; height is from node to deepest leaf