Binary Trees

# CHAPTER 19

Binary Trees #

1. Introduction #

2. Learning Objectives #

• Define the structural laws of a Binary Tree.

• Implement a Binary Node in code (left and right pointers).

• Execute Depth-First Search (DFS) traversals: Pre-order, In-order, Post-order.

• Execute Breadth-First Search (BFS) Level-order traversal.

• Understand the immense power of Recursion in Tree logic.

3. The Architecture: Left and Right #

// Java Example: The anatomy of a Binary Node
class Node {
    int data;
    Node left;  // Pointer to the Left Child
    Node right; // Pointer to the Right Child

    public Node(int item) {
        data = item;
        left = right = null; // Children are initially empty
    }
}

Visualizing a Binary Tree:

        [ 1 ]
       /     \
    [ 2 ]   [ 3 ]
   /    \
[ 4 ]  [ 5 ]

4. Tree Traversal Algorithms #

There are two massive families of Traversal Algorithms:

1. 1. Depth-First Search (DFS): Dive as deep as physically possible down a single branch until you hit a Leaf, then backtrack. (Uses Recursion/Stacks).

1. 2. Breadth-First Search (BFS): Read the tree horizontally, level by level, from top to bottom. (Uses Queues).

5. Depth-First Search (DFS) Traversals #

#### 5.1 Pre-order Traversal (Node, Left, Right)

1. 1. Print the current Node's data.

1. 2. Recursively travel down the Left branch.

1. 3. Recursively travel down the Right branch.

#### 5.2 In-order Traversal (Left, Node, Right)

1. 1. Recursively dive down the Left branch to the absolute bottom.

1. 2. Print the current Node's data.

1. 3. Recursively travel down the Right branch.

#### 5.3 Post-order Traversal (Left, Right, Node)

1. 1. Recursively dive down the Left branch.

1. 2. Recursively dive down the Right branch.

1. 3. Print the current Node's data.

# Python Example: The sheer elegance of DFS Recursive Traversals
def inorder_traversal(node):
    if node is None:
        return # Base Case: We fell off the tree!
        
    inorder_traversal(node.left)   # 1. Dive Left
    print(node.data, end=" ")      # 2. Print Center
    inorder_traversal(node.right)  # 3. Dive Right

6. Breadth-First Search (BFS) / Level-Order Traversal #

*Output of diagram above: 1, 2, 3, 4, 5*

// C++ Example: BFS Level-Order Traversal using a Queue
#include <iostream>
#include <queue>
using namespace std;

void levelOrderTraversal(Node* root) {
    if (root == NULL) return;

    queue<Node*> q;
    q.push(root); // Enqueue the top of the tree!

    while (!q.empty()) {
        Node* current = q.front();
        cout << current->data << " ";
        q.pop(); // Dequeue the node

        // If the left child exists, throw it in the back of the queue!
        if (current->left != NULL) q.push(current->left);
        
        // If the right child exists, throw it in the back of the queue!
        if (current->right != NULL) q.push(current->right);
    }
}

7. Complexity Analysis of Traversals #

• Time Complexity: O(n) Linear Time.

• Space Complexity (DFS): O(h) where h is the height of the tree (due to the OS Call Stack recursion depth).

• Space Complexity (BFS): O(w) where w is the maximum width of the tree (due to the size of the Queue).

8. Types of Binary Trees #

• Full Binary Tree: Every single node has either 0 children, or exactly 2 children. (No nodes with just 1 child).

• Complete Binary Tree: Every level is completely filled with nodes, except possibly the deepest level, which must be filled from left to right without gaps.

• Perfect Binary Tree: The absolute ultimate symmetry. Every internal node has 2 children, and every single leaf is on the exact same depth level.

9. Common Mistakes #

• Null Pointer Exceptions during Recursion: A junior developer will often write print(node.left.data) without checking if node.left actually exists. Always define the base case if (node == null) return; at the absolute top of the recursive function to securely handle falling off the tree.

10. Best Practices #

• Mental Modeling: When trying to understand a Recursive Tree algorithm, do not try to trace the entire tree in your head. You will get a headache. Only look at a microscopic Subtree consisting of exactly 3 nodes (A Parent, a Left Child, a Right Child). If the recursive algorithm works on those 3 nodes, it mathematically guarantees it will work on 3 billion nodes.

11. Exercises #

1. 1. Draw a generic, unbalanced Binary Tree with 6 nodes. Manually write out the sequence of numbers it would produce under Pre-order, In-order, and Post-order traversal.

1. 2. In the BFS Queue algorithm, why does it mathematically guarantee that Level 2 is processed before Level 3?

12. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Coding:* "Write a recursive algorithm to calculate the absolute Maximum Height (Depth) of a Binary Tree." *(Answer: return 1 + max(getHeight(node.left), getHeight(node.right))). This 1-line code blows interviewers' minds!*

• *Algorithmic Coding:* "Invert a Binary Tree. (Mirror it so all left nodes become right nodes, and vice versa)." *(Answer: The famous question that failed the creator of Homebrew at Google! Use Post-Order traversal. Dive to the bottom, and swap node.left and node.right on the way back up!)*

Common Pitfalls:

• In iterative BFS implementation, attempting to write queue.add(current.left) without wrapping it in an if (current.left != null) check. This will push NULL into your queue, crashing the loop on the next iteration.

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #