1. Triversal

---

🌳 Example Binary Tree

We will use the following binary tree for all tracing examples:

graph TD
    1((1)) --> 2((2))
    1 --> 3((3))
    2 --> 4((4))
    2 --> 5((5))

    classDef default fill:#1e1e2e,stroke:#cba6f7,stroke-width:2px,color:#cdd6f4;
    classDef root fill:#f38ba8,stroke:#e64553,stroke-width:2px,color:#11111b;
    class 1 root;

Traversal Outputs

• Preorder (Root → Left → Right): 1 2 4 5 3
• Inorder (Left → Root → Right): 4 2 5 1 3
• Postorder (Left → Right → Root): 4 5 2 3 1

---

Node Structure & Helpers

// ── NODE STRUCTURE ───────────────────────────────────────────────
struct node {
    int val;
    node* left;
    node* right;
    node(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};

---

🔄 Recursive Traversals

NOTE

All recursive traversals have a Time Complexity of $\mathcal{O}(N)$ as we visit each node exactly once. The Space Complexity is $\mathcal{O}(h)$ due to the recursion stack, where $h$ is the height of the tree (worst case $\mathcal{O}(N)$ for a skewed tree).

1. Preorder Traversal (Root → Left → Right)

void preorder(node* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

2. Inorder Traversal (Left → Root → Right)

void inorder(node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

3. Postorder Traversal (Left → Right → Root)

void postorder(node* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

---

⚙️ Iterative Traversals

1. Iterative Preorder

Uses a single stack. Since stacks are Last-In-First-Out (LIFO), we push the right child first and then the left child to process the left subtree first.

• Time Complexity: $\mathcal{O}(N)$
• Space Complexity: $\mathcal{O}(h)$ (worst case $\mathcal{O}(N)$ for skewed tree)

void it_pre(node* root) {    
    if (!root) return;
    stack<node*> st; 
    st.push(root);
 
    while (!st.empty()) {
        node* curr = st.top(); 
        st.pop();
        cout << curr->val << " ";
 
        // Push right child first so left child is processed first
        if (curr->right) st.push(curr->right);
        if (curr->left) st.push(curr->left);
    } 
}

---

2. Iterative Inorder

We traverse down to the leftmost node, pushing each node to the stack. Once we hit NULL, we pop from the stack (which gives us the parent/root node), print it, and move to its right subtree.

• Time Complexity: $\mathcal{O}(N)$
• Space Complexity: $\mathcal{O}(h)$ (worst case $\mathcal{O}(N)$ for skewed tree)

void it_in(node* root) {   
    stack<node*> st;
    while (true) {
        if (root) {
            st.push(root);
            root = root->left; // Go to leftmost node
        } else {
            if (st.empty()) break;
            root = st.top(); 
            st.pop(); // Root points to parent
            cout << root->val << " ";
            root = root->right; // Move to its right
        }
    }  
}

---

3. Iterative Postorder (Using 2 Stacks)

This is the easiest way to write iterative postorder. We modify the preorder approach (Root → Right → Left instead of Root → Left → Right) and push the elements onto a second stack (or vector). Reversing the final output gives us Left → Right → Root.

• Time Complexity: $\mathcal{O}(N)$
• Space Complexity: $\mathcal{O}(N)$ (additional space for storing nodes to reverse)

void it_post(node* root) {   
    if (!root) return;
    stack<node*> s;
    vector<int> v;
    s.push(root);
 
    while (!s.empty()) {
        node* curr = s.top(); 
        s.pop();
        v.push_back(curr->val);
 
        // Push left first, then right (opposite of preorder)
        if (curr->left) s.push(curr->left);
        if (curr->right) s.push(curr->right);
    }
    reverse(v.begin(), v.end());
    for (auto i : v) cout << i << " ";
}

---

4. Iterative Postorder (Using 1 Stack)

A more space-optimized approach that uses a single stack. It simulates the call stack by traveling to the leftmost node, then checking if there is a right child. If not, it processes the node and backtracks up.

WARNING

We must check !st.empty() in the nested while loop condition to prevent undefined behavior (segmentation fault) when popping the root node.

• Time Complexity: $\mathcal{O}(N)$
• Space Complexity: $\mathcal{O}(h)$ (worst case $\mathcal{O}(N)$ for skewed tree)

void it_post_2(node* root) {
    stack<node*> st;
    while (true) {
        if (root) {
            st.push(root);
            root = root->left; // (1) Go to leftmost
        } else {
            if (st.empty()) break;
 
            // (3) If right child is NULL, process the node
            if (st.top()->right == NULL) {
                root = st.top(); 
                st.pop();
                cout << root->val << " ";
 
                // (4) Special case: if root is the right child of its parent,
                // keep backtracking and printing parents.
                // Added '!st.empty()' guard to prevent out-of-bounds stack top access.
                while (!st.empty() && root == st.top()->right) {
                    root = st.top();
                    cout << root->val << " "; 
                    st.pop();
                }
            }
            // (2) If right child exists, move to it
            if (!st.empty()) root = st.top()->right; 
            else root = NULL;
        }
    }
}

---

🔀 All-in-One Traversal (Pre, In, Post in Single Pass)

By using a stack of pairs std::stack<std::pair<node*, int>>, we can track the state of each node traversal:

• state == 0: Preorder (Visit Node → Increment State → Push Left Child)
• state == 1: Inorder (Visit Node → Increment State → Push Right Child)
• state == 2: Postorder (Visit Node → Pop from Stack)

State	Order	Push Operation
0	Preorder	Left Child
1	Inorder	Right Child
2	Postorder	Nothing

• Time Complexity: $\mathcal{O}(3N)\approx \mathcal{O}(N)$
• Space Complexity: $\mathcal{O}(N)$

void pre_in_post(node* root) {
    if (!root) return; // Guard against NULL root
 
    stack<pair<node*, int>> st;
    st.push({root, 0});
    vector<int> pre, in, post;
 
    while (!st.empty()) {
        node* curr = st.top().first;
        int state = st.top().second; 
        st.pop();
 
        if (state == 0) {
            pre.push_back(curr->val);
            st.push({curr, state + 1});
            if (curr->left) st.push({curr->left, 0});
        } 
        else if (state == 1) {
            in.push_back(curr->val);
            st.push({curr, state + 1});
            if (curr->right) st.push({curr->right, 0});
        } 
        else {
            post.push_back(curr->val);
        }
    }
}

---