L5. Preorder Traversal of Binary Tree | C++ | Java | Code Explanation

1. Why Do We Need This? (Problem Statement & Status Quo)

When working with hierarchical data structures like binary trees, visiting every single node in a systematic and predictable order is a fundamental operation. Depth-First Search (DFS) traversal techniques allow us to explore a tree deeply down its branches before backtracking.

Among the primary DFS strategies—Preorder, Inorder, and Postorder—Preorder Traversal provides a systematic blueprint where the root node is processed before its subtrees. Understanding its coding implementation, recursive call stack behavior, time complexity, and space complexity is an essential stepping stone in mastering Data Structures and Algorithms (DSA).

2. Core Mental Model: The Preorder Rule

The golden rule of Preorder Traversal can be summarized in three words: Root, Left, Right.

• Root: Visit, process, or print the current node's data first.
• Left: Recursively traverse the entire left subtree.
• Right: Recursively traverse the entire right subtree.

          [Root]
          /    \
    [Left Subtree]  [Right Subtree]

3. Naive vs. Production Approach

Writing recursive tree traversals can sometimes feel intimidating if overcomplicated. The key is to keep the logic clean, minimal, and directly aligned with the traversal order.

The Clean Recursive Pattern

Instead of heavy boilerplate code, a Preorder Traversal function requires only a few core checks:

1. Base Case: If the current node is null, terminate the current recursive branch and return.
2. Action: Process/print the current node data (root.data).
3. Recursive Left: Call the traversal function on node.left.
4. Recursive Right: Call the traversal function on node.right.

4. Step-by-Step Code Implementation (C++ & Java)

The implementation patterns in both languages mirror each other closely due to their shared recursive nature.

C++ Implementation

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    
    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

void preorderTraversal(Node* node) {
    // Base Case: If node is null, return
    if (node == nullptr) {
        return;
    }
    
    // 1. Root: Process/Print current node
    cout << node->data << " ";
    
    // 2. Left: Traverse left subtree
    preorderTraversal(node->left);
    
    // 3. Right: Traverse right subtree
    preorderTraversal(node->right);
}

Java Implementation

class Node {
    int data;
    Node left;
    Node right;
    
    Node(int val) {
        data = val;
        left = null;
        right = null;
    }
}

class BinaryTreeTraversal {
    public static void preorderTraversal(Node node) {
        // Base Case: If node is null, return
        if (node == null) {
            return;
        }
        
        // 1. Root: Process/Print current node
        System.out.print(node.data + " ");
        
        // 2. Left: Traverse left subtree
        preorderTraversal(node.left);
        
        // 3. Right: Traverse right subtree
        preorderTraversal(node.right);
    }
}

5. Complete Flow Walkthrough (Dry Run on a Sample Tree)

Let us perform a detailed dry run to understand how the recursive call stack executes a Preorder Traversal. Consider a binary tree structured as follows:

          1
        /   \
       2     3
      / \   / \
     4   5 7   8
        /       \
       6         9
                  \
                  10

Execution Trace Step-by-Step:

1. Call preorderTraversal(1):

   • 1 is not null. Print 1.
   • Call left child: preorderTraversal(2).

2. Inside preorderTraversal(2):

   • 2 is not null. Print 2.
   • Call left child: preorderTraversal(4).

3. Inside preorderTraversal(4):

   • 4 is not null. Print 4.
   • Call left child of 4 (null) -> returns immediately.
   • Call right child of 4 (null) -> returns immediately.
   • Recursion for 4 is complete. Returns back to 2.

4. Back in preorderTraversal(2):

   • Left subtree is done. Now call right child: preorderTraversal(5).

5. Inside preorderTraversal(5):

   • 5 is not null. Print 5.
   • Call left child: preorderTraversal(6).

6. Inside preorderTraversal(6):

   • 6 is not null. Print 6.
   • Call left child (null) -> returns.
   • Call right child (null) -> returns.
   • Recursion for 6 is complete. Returns back to 5.

7. Back in preorderTraversal(5):

   • Left done, call right child (null) -> returns.
   • Recursion for 5 is complete. Returns back to 2.

8. Back in preorderTraversal(2):

   • Root, left, and right are all completed for 2. Returns back to root 1.

9. Back in preorderTraversal(1):

   • Left subtree of 1 is completely finished. Now call right child: preorderTraversal(3).

10. Inside preorderTraversal(3):

    • 3 is not null. Print 3.
    • Call left child: preorderTraversal(7).
    • (Traversal continues down through 7, 8, 9, and 10 following the Root -> Left -> Right rule).

Final Preorder Output Sequence:

1 -> 2 -> 4 -> 5 -> 6 -> 3 -> 7 -> 8 -> 9 -> 10

6. Time and Space Complexity Analysis

Evaluating algorithm performance is critical for production-ready code.

7. Real-World Practical Pitfalls & Debugging Mindset

• Forgetting the Base Case: Omitting if (node == nullptr) or if (node == null) leads directly to a NullPointerException (Java) or Segmentation Fault (C++) because the recursion will attempt to access properties of a non-existent node indefinitely.
• Misplacing the Print Statement: Putting the print statement after the left and right recursive calls changes the algorithm from Preorder to Postorder. Always double-check that the print action happens before diving into child nodes.
• Stack Overflow on Skewed Trees: Be mindful of extremely unbalanced trees (e.g., where every node only has a right child). The recursive call stack depth will match the number of nodes, risking a stack overflow in languages/environments with strict stack size limits.

8. Summary and Key Takeaways

• Preorder Traversal Strategy: Follows the Root, Left, Right sequence where the parent node is always visited and processed before its children.
• Simplicity is Key: Avoid overcomplicating recursive functions; three core lines handle base checks, printing, and left/right recursive calls.
• Recursion & Call Stack: The function relies heavily on the call stack to remember where to return after exhausting a left or right subtree branch.
• Linear Time Performance: Achieves an optimal $O(N)$ time complexity as each node is visited once.
• Height-Dependent Space: Auxiliary space complexity is proportional to the height of the tree ($O(H)$), scaling up to $O(N)$ in worst-case skewed trees.
• Universal Application: The same structural pattern applies across both C++ and Java with minimal syntax adjustments.