#include <stdio.h>
#include <stdlib.h>
 
// Binary Tree Node Structure
struct Node {
    int data;
    struct Node *left, *right;
};
 
// Stack structure to simulate recursion
struct Stack {
    int top;
    int capacity;
    struct Node **array;
};
 
// Function to create a new tree node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
 
// Function to create a stack
struct Stack* createStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->top = -1;
    stack->capacity = capacity;
    stack->array = (struct Node**)malloc(stack->capacity * sizeof(struct Node*));
    return stack;
}
 
// Stack utility functions
int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}
 
void push(struct Stack* stack, struct Node* node) {
    stack->array[++stack->top] = node;
}
 
struct Node* pop(struct Stack* stack) {
    if (isEmpty(stack))
        return NULL;
    return stack->array[stack->top--];
}
 
// Iterative Inorder Traversal
void inorderTraversal(struct Node* root) {
    struct Stack* stack = createStack(100); // Allocate stack space
    struct Node* current = root;
 
    printf("Inorder Traversal (Iterative): ");
 
    while (current != NULL || !isEmpty(stack)) {
        // Reach the leftmost node of the current node
        while (current != NULL) {
            push(stack, current);
            current = current->left;
        }
 
        // Pop from stack and visit node
        current = pop(stack);
        printf("%d ", current->data);
 
        // Visit the right subtree
        current = current->right;
    }
 
    printf("\n");
}
 
// Main function
int main() {
    /*
              1
             / \
            2   3
           / \
          4   5
    */
 
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
 
    inorderTraversal(root);
 
    return 0;
}