Tree Properties

1. Introduction: The Shape of the Data

When working with Binary Trees, the shape of the tree is often just as important as the data inside it. A tree that looks like a straight line (a Linked List) has an $O(N)$ lookup time. A perfectly balanced tree has an $O(\log N)$ lookup time.

Understanding how to calculate and verify structural properties—like Height, Balance, and Symmetry—is the absolute foundation of all Tree algorithms. If you can confidently write a recursive function to find the maximum depth of a tree, you can solve 80% of all easy-to-medium Tree interview questions.

2. Core Concept: Bottom-Up Recursion

Most structural properties are calculated using Bottom-Up Recursion (Post-Order Traversal). Instead of passing information down the tree, you dive all the way to the leaf nodes. The leaf nodes answer a simple question (e.g., "My height is 1"). They pass that answer up to their parent. The parent combines the answers from its left and right children, adds its own data, and passes the new answer further up!

3. Beginner Code Example: Maximum Depth (Height)

Problem Statement: (LeetCode 104) Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

The Insight: What is the height of a parent node? It is 1 (for itself) plus the maximum of the heights of its left and right children!

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class MaxDepth {
    public int maxDepth(TreeNode root) {
        // Base Case: An empty space has a height of 0
        if (root == null) {
            return 0;
        }
        
        // 1. Ask the left child for its height
        int leftHeight = maxDepth(root.left);
        
        // 2. Ask the right child for its height
        int rightHeight = maxDepth(root.right);
        
        // 3. Return 1 (for the current node) + the taller child
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We visit every node exactly once.
• Space Complexity: $O(H)$ where $H$ is the height of the tree, for the recursion stack. (Worst case $O(N)$ for a skewed tree, best case $O(\log N)$ for a balanced tree).

4. Intermediate Code Example: Balanced Binary Tree

Problem Statement: (LeetCode 110) Given a binary tree, determine if it is height-balanced. 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.

The Naive Trap ($O(N^2)$): Calling maxDepth(root.left) and maxDepth(root.right), checking the difference, and then recursively calling isBalanced() on the children. This recalculates heights over and over!

The Elite Insight ($O(N)$): Since maxDepth is already doing a bottom-up traversal, we can hijack it! While calculating the height, if a node realizes its left and right subtrees differ by $>1$, it instantly returns -1 (a sentinel value) to indicate the tree is unbalanced. If any parent sees a -1 coming from a child, it instantly passes -1 up the chain.

public class BalancedTree {
    public boolean isBalanced(TreeNode root) {
        // If the helper returns anything other than -1, the tree is balanced.
        return checkHeight(root) != -1;
    }
    
    private int checkHeight(TreeNode node) {
        if (node == null) return 0;
        
        int leftHeight = checkHeight(node.left);
        if (leftHeight == -1) return -1; // Left subtree is broken, abort!
        
        int rightHeight = checkHeight(node.right);
        if (rightHeight == -1) return -1; // Right subtree is broken, abort!
        
        // Calculate the difference
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1; // This node breaks the balance rule! Abort!
        }
        
        // Otherwise, return the actual height normally
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

5. Advanced Code Example: Symmetric Tree

Problem Statement: (LeetCode 101) Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

The Insight: A tree is symmetric if the left subtree is a mirror reflection of the right subtree. To prove this, we must compare two nodes simultaneously (Left and Right).

• The outer branches must match: Left.left must match Right.right.
• The inner branches must match: Left.right must match Right.left.

public class SymmetricTree {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        // Launch a helper that compares the left and right sides simultaneously
        return isMirror(root.left, root.right);
    }
    
    private boolean isMirror(TreeNode t1, TreeNode t2) {
        // Base case: Both hit null at the same time. Perfectly symmetric!
        if (t1 == null && t2 == null) return true;
        
        // Mismatch cases: One hit null early, or values don't match
        if (t1 == null || t2 == null) return false;
        if (t1.val != t2.val) return false;
        
        // Check outer branches AND inner branches
        boolean outerSymmetric = isMirror(t1.left, t2.right);
        boolean innerSymmetric = isMirror(t1.right, t2.left);
        
        return outerSymmetric && innerSymmetric;
    }
}

6. Common Mistakes Beginners Make

1. Confusing Height and Depth

   • The Mistake: Using the terms interchangeably.
   • The Reality:
     • Depth is measured from the Root down to a node (Root is depth 0).
     • Height is measured from a Leaf up to a node (Leaf is height 0, or 1 depending on convention).
     • The "Maximum Depth" of a tree is mathematically equal to the "Height" of the Root.

2. $O(N^2)$ Balanced Tree Checks

   • The Mistake: Writing Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);.
   • Why it's wrong: You traverse the entire tree to get the depth. Then you step down to the left child, and traverse the entire left tree again to get its depth. This creates an $O(N^2)$ nightmare. Always combine height calculations with rule verifications using sentinel values like -1.

3. Checking Symmetry sequentially instead of simultaneously

   • The Mistake: Trying to do an In-Order traversal, putting the values in an array, and checking if the array is a palindrome.
   • Why it's wrong: [1, 2, 2, 2, null, 2] will generate a palindromic array, but the structure is completely unsymmetrical! You MUST compare the actual nodes simultaneously.

7. Interview Q&A

Q1: How do you find the Diameter of a Binary Tree? (LeetCode 543) Answer: The diameter is the longest path between ANY two nodes. The path might not go through the root! We solve it by hijacking the maxDepth function again. Inside maxDepth, the diameter passing through the current node is leftHeight + rightHeight. We maintain a global maxDiameter variable and update it at every node during our bottom-up traversal.

Q2: Can Symmetric Tree be solved iteratively? Answer: Yes, using a Queue (like BFS). You enqueue the left and right children in pairs. You dequeue two nodes at a time, verify their values, and then carefully enqueue their children in the correct mirrored order: (t1.left, t2.right) then (t1.right, t2.left).

8. Practice Problems

1. Maximum Depth of Binary Tree (LeetCode 104)
   • Goal: Perfect the basic bottom-up height template.
2. Balanced Binary Tree (LeetCode 110)
   • Goal: Master the $O(N)$ early-abort -1 sentinel trick.
3. Diameter of Binary Tree (LeetCode 543)
   • Hint: Combine height calculation with a global max update.
4. Symmetric Tree (LeetCode 101)
   • Goal: Master simultaneous two-node recursion.

9. Summary

• Bottom-Up Traversal: Dive to null (return 0), then calculate answers as the stack unwinds back to the root.
• The Height Formula: 1 + Math.max(left, right).
• Optimization: Never do an $O(N)$ tree traversal inside another recursive tree function. Hijack the traversal to return dual information (like height + balance state).
• Simultaneous Recursion: For symmetry or identical tree checks, pass (node1, node2) and recurse on (node1.left, node2.right).