Tree Traversal Preorder Root Left Right in DSA C++

Mental Model

Visit the root node first, then explore the left subtree, and finally the right subtree. This order helps you see the tree starting from the top and going down left before right.

Analogy: Imagine reading a family tree starting from the oldest ancestor (root), then looking at their left child and all descendants, before moving to the right child and their descendants.

    1
   / \
  2   3
 / \
4   5

↑ Root at 1

Dry Run Walkthrough

Input: Tree: 1 as root, 2 as left child, 3 as right child, 4 as left child of 2, 5 as right child of 2

Goal: Print nodes in preorder: root first, then left subtree, then right subtree

Step 1: Visit root node 1

Output: 1

Why: Start traversal at the root node

Step 2: Traverse left subtree starting at node 2

Output: 1 2

Why: After root, preorder visits left subtree

Step 3: Visit left child of 2, node 4

Output: 1 2 4

Why: Preorder visits root of left subtree before its children

Step 4: Back to node 2, visit right child 5

Output: 1 2 4 5

Why: After left child, visit right child in left subtree

Step 5: Traverse right subtree starting at node 3

Output: 1 2 4 5 3

Why: After left subtree, preorder visits right subtree

Result:

Output: 1 2 4 5 3

Annotated Code

DSA C++

#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* root) {
    if (root == nullptr) return; // base case: no node
    cout << root->data << " "; // visit root first
    preorderTraversal(root->left); // then traverse left subtree
    preorderTraversal(root->right); // finally traverse right subtree
}

int main() {
    // build tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    preorderTraversal(root);
    cout << endl;
    return 0;
}

if (root == nullptr) return; // base case: no node

stop recursion when no node to visit

cout << root->data << " "; // visit root first

visit current node before children

preorderTraversal(root->left); // then traverse left subtree

recursively visit left subtree

preorderTraversal(root->right); // finally traverse right subtree

recursively visit right subtree

Output

1 2 4 5 3 

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to inorder or postorder, preorder visits root first which is useful for copying or prefix expressions

Edge Cases

Empty tree (root is nullptr)

No output, function returns immediately

DSA C++

if (root == nullptr) return; // base case: no node

Single node tree

Only root node is printed

DSA C++

if (root == nullptr) return; // base case: no node

Tree with only left children

Nodes printed top to bottom along left side

DSA C++

preorderTraversal(root->left); // then traverse left subtree

When to Use This Pattern

When you need to process the root before its children, such as copying a tree or prefix expression evaluation, use preorder traversal.

Common Mistakes

Mistake: Visiting left or right child before the root node
Fix: Print the root node's data before recursive calls to children

Mistake: Not checking for nullptr before recursion causing crashes
Fix: Add base case to return immediately if node is nullptr

Summary

Visits the root node first, then left subtree, then right subtree.

Use when you want to process the root before its children, like copying or prefix operations.

Remember: root first, then left, then right.