Problem Statement

Given a binary tree with root node. Return the In-order, Pre-order and Post-order traversal of the binary tree.

Examples

Example 1:

Input: root = [1, 3, 4, 5, 2, 7, 6]
Output: [
         [5, 3, 2, 1, 7, 4, 6],
         [1, 3, 5, 2, 4, 7, 6],
         [5, 2, 3, 7, 6, 4, 1]
        ]

Explanation:
The In-order traversal is : [5, 3, 2, 1, 7, 4, 6]
The Pre-order traversal is : [1, 3, 5, 2, 4, 7, 6]
The Post-order traversal is : [5, 2, 3, 7, 6, 4, 1]

Different Approaches

1️⃣ Using Stack Data Structure

Intuition:

A binary tree's preorder, in-order, and post-order traversals typically require three separate traversals. This can be obtained in a single pass using a stack for state management. The stack tracks the traversal state for each node. In the preorder state, the node's value is recorded, and its left child is pushed onto the stack. In the inorder state, the node's value is recorded, and its right child is pushed onto the stack. In the postorder state, the node's value is recorded, and the node is popped from the stack. This process pushes each value into separate arrays for preorder, in-order, and post-order traversals, enabling a single traversal to compute all three orders.

Approach:

1. Create three vectors to store the results of Preorder, Inorder, and Postorder traversals. Use a stack to keep track of nodes and their traversal states. Start with the root node and a state of 1 (indicating Preorder).While the stack is not empty, pop the top element from the stack.
2. If the state is 1 (Preorder), add the node's data to the Preorder vector, change the state to 2 (Inorder) and push the node back onto the stack. If the node has a left child, push it onto the stack with a state of 1.
3. If the state is 2 (Inorder), add the node's data to the Inorder vector. change the state to 3 (Postorder) and push the node back onto the stack. If the node has a right child, push it onto the stack with a state of 1.
4. If the state is 3 (Post-order), Add the node's data to the Post-order vector. Return the vectors containing the Preorder, In-order, and Post-order traversals.

Code:

#include <bits/stdc++.h>
using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int data;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
 * };
 **/

class Solution {
public:
    vector<vector<int>> treeTraversal(TreeNode* root) {
        // Vectors to store the traversals
        vector<int> pre, in, post;

        // If the tree is empty, return empty traversals
        if (root == nullptr) return { pre, in, post };

        // Stack to maintain nodes and their traversal state
        stack<pair<TreeNode*, int>> st;

        // Start with the root node and state 1 (preorder)
        st.push({ root, 1 });

        while (!st.empty()) {
            // Get the top element from the stack
            auto [node, state] = st.top();
            st.pop();

            // Process the node based on its state
            if (state == 1) {
                // Preorder: Add node data
                pre.push_back(node->data);
                // Change state to 2 (inorder) for this node
                st.push({ node, 2 });

                // Push left child onto the stack for processing
                if (node->left != nullptr) {
                    st.push({ node->left, 1 });
                }
            } else if (state == 2) {
                // Inorder: Add node data
                in.push_back(node->data);
                // Change state to 3 (postorder) for this node
                st.push({ node, 3 });

                // Push right child onto the stack for processing
                if (node->right != nullptr) {
                    st.push({ node->right, 1 });
                }
            } else {
                // Postorder: Add node data
                post.push_back(node->data);
            }
        }

        // Return the traversals as a 2D vector
        return { in, pre, post};
    }
};

// Main function to test the tree traversal
int main() {
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    Solution sol;
    vector<vector<int>> traversals = sol.treeTraversal(root);

    // Print Preorder traversal
    cout << "Preorder traversal: ";
    for (int val : traversals[0]) cout << val << " ";
    cout << endl;

    // Print Inorder traversal
    cout << "Inorder traversal: ";
    for (int val : traversals[1]) cout << val << " ";
    cout << endl;

    // Print Postorder traversal
    cout << "Postorder traversal: ";
    for (int val : traversals[2]) cout << val << " ";
    cout << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(3N), where N is the number of nodes, since each node is processed three times (preorder, inorder, postorder).
• Space Complexity: O(4N), where N is the number of nodes, due to the stack and three traversal arrays.