3.7) Iterative Preorder Traversal of Binary Tree

Given a binary tree, write a program to perform an iterative preorder traversal and print the values of the nodes as they are visited. In a preorder traversal, we visit the root node first, then the left subtree, and finally the right subtree.

Consider the following binary tree:

    1
   / \
  2   3
     / \
    4   5

Expected Output:
The expected output for the iterative preorder traversal of the given binary tree is: 1 2 3 4 5.

Iterative Preorder Traversal C++:

#include <iostream>
#include <stack>

using namespace std;

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

// Function to perform iterative preorder traversal
void iterativePreOrderTraversal(TreeNode* root) {
    if (!root)
        return;

    stack<TreeNode*> st;
    st.push(root);

    while (!st.empty()) {
        TreeNode* current = st.top();
        st.pop();
        cout << current->val << " ";

        // Push the right subtree first to ensure left subtree is processed first
        if (current->right)
            st.push(current->right);
        if (current->left)
            st.push(current->left);
    }
}

int main() {
    // Create the binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(5);

    // Perform iterative preorder traversal
    cout << "Iterative Preorder Traversal: ";
    iterativePreOrderTraversal(root);
    cout << endl;

    return 0;
}

Time and Space Complexity:

The time complexity of the iterative preorder traversal is O(n), where n is the number of nodes in the binary tree, since we visit each node once.

The space complexity is O(h), where h is the height of the binary tree.

In the worst case (skewed tree), the space complexity could be O(n), and in the best case (balanced tree), it could be O(log n).

Code Explanation:

In this program, the iterativePreOrderTraversal function performs the iterative preorder traversal using a stack. It starts by pushing the root node onto the stack. Then, it enters a loop where it pops a node from the stack, visits it, and pushes its right and left subtrees onto the stack (right subtree first to ensure left subtree is processed first).

The main function creates a binary tree, calls the iterativePreOrderTraversal function, and prints the preorder traversal of the tree.