30. DSA with C++ - Inorder Traversal with Recursion and without Recursion

Algorithm

1. Create an empty stack and set the current node as the root of the tree.
2. Repeat the following steps until the current node is null and the stack is empty:
   
   Traverse the left subtree by pushing each node onto the stack until reaching the lemost leaf node.
   
   Process the current node by printing its data and popping it from the stack.
   
   Set the current node as the right child of the popped node.
   
   
3. Set the current node as the right child of the popped node.
4. Repeat steps 2 and 3 unl all nodes have been processed.

Inorder Traversal With Recursion

#include <iostream>

// Define a basic structure for a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Recursive function to perform an inorder traversal
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    // Recursively traverse the left subtree
    inorderTraversal(root->left);

    // Visit the current node
    std::cout << root->data << " ";

    // Recursively traverse the right subtree
    inorderTraversal(root->right);
}

int main() {
    // Create 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);

    // Perform an inorder traversal starting from the root
    std::cout << "Inorder Traversal: ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}
    

Inorder Traversal Without Recursion

#include <iostream>
#include <stack>

// Define a basic structure for a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Iterative function to perform an inorder traversal without recursion
void inorderTraversalWithoutRecursion(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    std::stack<TreeNode*> nodeStack;
    TreeNode* currentNode = root;

    while (!nodeStack.empty() || currentNode != nullptr) {
        // Traverse to the leftmost node while pushing nodes onto the stack
        while (currentNode != nullptr) {
            nodeStack.push(currentNode);
            currentNode = currentNode->left;
        }

        // Visit the current node and move to the right subtree
        currentNode = nodeStack.top();
        nodeStack.pop();
        std::cout << currentNode->data << " ";
        currentNode = currentNode->right;
    }
}

int main() {
    // Create 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);

    // Perform an inorder traversal without recursion starting from the root
    std::cout << "Inorder Traversal (Without Recursion): ";
    inorderTraversalWithoutRecursion(root);
    std::cout << std::endl;

    return 0;
}