Binary Tree Traversal Algorithms

# CHAPTER 5

Binary Tree Traversal Algorithms #

1. Introduction #

2. Learning Objectives #

• Define the root-centric naming convention of traversal algorithms.

• Execute Inorder, Preorder, and Postorder traversal paths on a visual tree.

• Write blistering-fast recursive code functions to execute all three traversals.

• Understand the real-world utility of each specific traversal pattern.

3. The Core Concept (Depth-First Search) #

The Naming Trick: The prefix (In, Pre, Post) specifically tells you exactly when to process the ROOT (the current node).

• Preorder: Process the node BEFORE its children.

• Inorder: Process the node IN BETWEEN its left and right children.

• Postorder: Process the node AFTER both children are finished.

4. Inorder Traversal (Left, Root, Right) #

1. 1. Traverse the entire Left Subtree.

1. 2. Process/Print the Current Node (Root).

1. 3. Traverse the entire Right Subtree.

Real-World Application: When executed on a Binary Search Tree (BST), an Inorder traversal mathematically guarantees the data will be printed in perfect Ascending Sorted Order (e.g., 1, 2, 3, 4, 5).

5. Preorder Traversal (Root, Left, Right) #

1. 1. Process/Print the Current Node (Root) immediately.

1. 2. Traverse the entire Left Subtree.

1. 3. Traverse the entire Right Subtree.

Real-World Application: Used to create an exact Copy (Clone) of a tree. By grabbing the parent node first before exploring the children, you can seamlessly reconstruct the geometric structure top-down.

6. Postorder Traversal (Left, Right, Root) #

1. 1. Traverse the entire Left Subtree.

1. 2. Traverse the entire Right Subtree.

1. 3. Process/Print the Current Node (Root) last.

Real-World Application: Used to completely Delete a tree from RAM. You cannot safely delete a parent node until you have definitively erased all of its children, making a bottom-up sweep absolutely mandatory.

7. Step-by-Step Traversal Walkthrough #

        A
       / \
      B   C
     / \
    D   E

1. Inorder (Left, Root, Right): Plunge extreme left to D. Print D. Go back to B. Print B. Go right to E. Print E. Go back to A. Print A. Go right to C. Print C. *Output:* D -> B -> E -> A -> C

2. Preorder (Root, Left, Right): Start at A. Print A. Go left to B. Print B. Go left to D. Print D. Backtrack, go right to E. Print E. Backtrack, go right to C. Print C. *Output:* A -> B -> D -> E -> C

3. Postorder (Left, Right, Root): Plunge left to D. Print D. Go to B's right child E. Print E. Both B's children are done, so print B. Go to A's right side C. Print C. Both A's children are done, print A. *Output:* D -> E -> B -> C -> A

8. Code Execution (Recursion) #

Java:

class Traversal {
    // INORDER
    void printInorder(Node node) {
        if (node == null) return; // Base Case
        printInorder(node.left);
        System.out.print(node.data + " ");
        printInorder(node.right);
    }

    // PREORDER
    void printPreorder(Node node) {
        if (node == null) return; // Base Case
        System.out.print(node.data + " "); // Print FIRST
        printPreorder(node.left);
        printPreorder(node.right);
    }

    // POSTORDER
    void printPostorder(Node node) {
        if (node == null) return; // Base Case
        printPostorder(node.left);
        printPostorder(node.right);
        System.out.print(node.data + " "); // Print LAST
    }
}

9. Complexity Analysis #

• Time Complexity: $O(N)$. Every single algorithm visits every single node exactly once.

• Space Complexity: $O(H)$ where $H$ is the height of the tree. This is caused by the OS Call Stack piling up recursive function layers as it plunges down a path.

10. Common Mistakes #

• Forgetting the Base Case: If you omit if (node == null) return;, your algorithm will aggressively try to read the left child of a null pointer, instantly triggering a massive application crash (Null Pointer Exception).

11. Exercises #

1. 1. Draw a random tree with 7 nodes. Manually write down the Inorder, Preorder, and Postorder sequences.

1. 2. Given a Postorder array [4, 5, 2, 3, 1], identify the absolute Root node of the tree.

12. MCQs with Answers #

Q10. True or False: You can write Inorder, Preorder, and Postorder traversals iteratively using a while loop instead of Recursion. a) True. By manually initializing your own Stack data structure to simulate the OS Call Stack, you can execute all DFS traversals completely iteratively. b) False. They strictly require recursion. Answer: a) True. By manually initializing your own Stack data structure...

13. Interview Questions #

• Q: Write an Iterative Inorder traversal algorithm without using any recursion. *(Answer: Use a standard while loop and initialize a manual Stack object to push and pop parent nodes as you dive left!)*

• Q: How do you clone a Binary Tree? *(Answer: Use Preorder traversal to instantiate the parent root, then recursively attach the cloned left and right subtrees).*

14. Summary #

15. Next Chapter Recommendation #