Trees and Binary Trees

# CHAPTER 10

Trees and Binary Trees #

1. Chapter Introduction #

2. Anatomy of a Binary Tree #

• Root: The top node of the tree.

• Leaf: A node with zero children (the bottom of the tree).

• Depth: The number of edges from the root down to a specific node.

• Height: The maximum depth of the tree.

*The Node Class:*

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

3. Tree Traversal: Depth-First Search (DFS) #

There are 3 ways to order a DFS traversal. Given a tree:

      1
     / \
    2   3

1. 1. Pre-Order (Node, Left, Right): [1, 2, 3]. Visit the node first. Good for copying a tree.

1. 2. In-Order (Left, Node, Right): [2, 1, 3]. Visits nodes left-to-right. (Crucial for Binary Search Trees).

1. 3. Post-Order (Left, Right, Node): [2, 3, 1]. Visit children before the parent. Good for deleting a tree.

*Standard DFS Template (In-Order):*

def inOrderTraversal(root):
    res = []
    
    def dfs(node):
        if not node: # Base Case: We hit the bottom
            return
            
        dfs(node.left)    # Go Left
        res.append(node.val) # Process Node
        dfs(node.right)   # Go Right
        
    dfs(root)
    return res
# Time: O(N), Space: O(H) where H is the height of the tree (Call Stack)

4. Tree Traversal: Breadth-First Search (BFS) #

*Standard BFS Template (Level Order Traversal):*

from collections import deque

def levelOrder(root):
    if not root: return []
    
    res = []
    queue = deque([root]) # 1. Initialize queue with root
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        # 2. Process all nodes on the CURRENT level
        for _ in range(level_size):
            node = queue.popleft() # Dequeue
            current_level.append(node.val)
            
            # 3. Add children to queue for the NEXT level
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
            
        res.append(current_level)
        
    return res
# Time: O(N), Space: O(W) where W is the max width of the tree

5. Pattern 1: Maximum Depth of Binary Tree #

public int maxDepth(TreeNode root) {
    // Base case: An empty tree has depth 0
    if (root == null) return 0;
    
    // Recursive calls down left and right subtrees
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    
    // The answer is 1 (current node) + the larger of the two subtrees
    return Math.max(leftDepth, rightDepth) + 1;
}

*Why this is beautiful:* You don't need to track the global state. You define the rule for a single node, and recursion applies it to the entire tree.

6. Pattern 2: Tree Equality / Symmetry #

1. 1. Both nodes are null (True).

1. 2. One is null, the other isn't (False).

1. 3. The values are different (False).

1. 4. isSameTree(p.left, q.left) AND isSameTree(p.right, q.right) are both True.

7. Real-World Scenario: DOM Traversal #

8. Mini Project: Invert a Binary Tree #

1. 1. If root is null, return.

1. 2. Swap root.left and root.right.

1. 3. Recursively call invertTree(root.left) and invertTree(root.right).

1. 4. Return root.

9. Common Mistakes #

• Forgetting the Base Case: Every recursive tree function MUST start with if not root: return .... If you forget this, the recursion will attempt to access null.left, throwing a NullPointerException.

• Global Variables: Trying to maintain a global count variable outside the recursive function. Interviewers hate this. Learn to return values *up* the recursive call stack.

10. Best Practices #

• Time Complexity: Tree traversal is almost always O(N) Time because you must visit every node exactly once.

• Space Complexity: Recursion is NOT O(1) Space. Every recursive call adds a frame to the system Call Stack. The space complexity is O(H), where H is the height of the tree. (In worst-case unbalanced trees, H = N).

11. Exercises #

1. 1. Trace the Post-Order traversal of a tree with Root 1, Left 2, Right 3.

1. 2. In the BFS Queue template, why do we calculate levelsize = len(queue) before the inner for loop?

14. Interview Questions #

• Q: "Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level in a 2D array)." (LeetCode 102).

15. FAQs #

• Q: Which is better, DFS or BFS?

16. Summary #

17. Next Chapter Recommendation #