#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 10

// Tree node structure
typedef struct _Node *NodePtr;
typedef struct _Node {
    int data;
    NodePtr left;
    NodePtr right;
} Node;

// Function to create a new node
NodePtr new_node(int data) {
    NodePtr node = (NodePtr)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Function to insert a node into the tree
NodePtr insert(NodePtr node, int data) {
    if (node == NULL) return new_node(data);
    if (data < node->data)
        node->left = insert(node->left, data);
    else
        node->right = insert(node->right, data);
    return node;
}

NodePtr insert_skewed(NodePtr node, int data, int skewed_direction) {
    if (node == NULL) return new_node(data);
    if (skewed_direction == 1)
        node->left = insert_skewed(node->left, data, skewed_direction);
    else if (skewed_direction == 2)
        node->right = insert_skewed(node->right, data, skewed_direction);
    return node;
}

// Function to print the tree in preorder
void preorder(NodePtr root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// Function to print the tree in inorder
void inorder(NodePtr root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

// Function to print the tree in postorder
void postorder(NodePtr root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

// Function to print the tree in level order
void print_level(NodePtr root, int level) {
    if (root == NULL) return;
    if (level == 1)
        printf("%d ", root->data);
    else if (level > 1) {
        print_level(root->left, level - 1);
        print_level(root->right, level - 1);
    }
}

void levelorder(NodePtr root, int height) {
    int i;
	for (i = 1; i <= height; i++)
        print_level(root, i);
}

// Function to get the height of the tree
int get_height(NodePtr root) {
    if (root == NULL) return 0;
    int leftHeight = get_height(root->left);
    int rightHeight = get_height(root->right);
    return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}

// Function to perform iterative preorder traversal
void iterative_preorder(NodePtr root) {
    NodePtr stack[SIZE];
    int top = -1;

    if (root != NULL) {
        stack[++top] = root;

        while (top != -1) {
            NodePtr current = stack[top--];
            printf("%d ", current->data);

            if (current->right != NULL) {
                stack[++top] = current->right;
            }

            if (current->left != NULL) {
                stack[++top] = current->left;
            }
        }
    }
}

// Function to perform iterative inorder traversal
void iterative_inorder(NodePtr root) {
    NodePtr stack[SIZE];  // Assuming the maximum stack size is SIZE
    int top = -1;
    NodePtr current = root;

    while (current != NULL || top != -1) {
        while (current != NULL) {
            stack[++top] = current;
            current = current->left;
        }

        current = stack[top--];
        printf("%d ", current->data);

        current = current->right;
    }
}

// Function to perform iterative postorder traversal
void iterative_postorder(NodePtr root) {
    NodePtr stack1[SIZE], stack2[SIZE];
    int top1 = -1, top2 = -1;

    if (root != NULL) {
        stack1[++top1] = root;

        while (top1 != -1) {
            NodePtr current = stack1[top1--];
            stack2[++top2] = current;

            if (current->left != NULL) {
                stack1[++top1] = current->left;
            }

            if (current->right != NULL) {
                stack1[++top1] = current->right;
            }
        }

        while (top2 != -1) {
            printf("%d ", stack2[top2--]->data);
        }
    }
}

// Function to generate random numbers and insert them into the tree
NodePtr generate_tree(int size) {
    int element_in_one_line = 5;

    int range = 100, offset = 1, len = size;
    srand(time(NULL));
    NodePtr root = NULL;
    int i;
	for (i = 0; i < len; i++) {
        int num = rand() % range + offset;
        printf("%d ", num);
        if ((i + 1) % element_in_one_line == 0) printf("\n");
        root = insert(root, num);
    }
    return root;
}

// Function to generate random numbers and insert them into the tree by skewed factor
NodePtr generate_skewed_tree(int size, int skew_factor) {    // 1 for left skewed, 2 for right skewed
    int range = 100, offset = 1;
    int element_in_one_line = 5;
    srand(time(NULL));

    NodePtr root = NULL;
    int i;
	for (i = 0; i < size; i++) {
        int num = rand() % range + offset;

        if (skew_factor == 1) {
            // Insert into left-skewed tree
            root = insert_skewed(root, num, 1);
        } else if (skew_factor == 2) {
            // Insert into right-skewed tree
            root = insert_skewed(root, num, 2);
        }

        printf("%d ", num);
        if ((i + 1) % element_in_one_line == 0) printf("\n");
    }
    return root;
}


int main() {
    // (a) Generate random numbers, print it and insert into the tree
    NodePtr root = generate_skewed_tree(SIZE, 2);    // 1 for left skewed, 2 for right skewed
    printf("\n");

    // (b) Preorder traversal
    printf("Preorder traversal:\n");
    preorder(root);
    printf("\n\n");

    // (c) Inorder traversal
    printf("Inorder traversal:\n");
    inorder(root);
    printf("\n\n");

    // (d) Postorder traversal
    printf("Postorder traversal:\n");
    postorder(root);
    printf("\n\n");

    // (e) Level order traversal
    printf("Level order traversal:\n");
    levelorder(root, get_height(root));
    printf("\n\n");

    // (f) Iterative inorder traversal
    printf("Iterative inorder traversal:\n");
    iterative_inorder(root);
    printf("\n\n");

    // (*) Iterative preorder traversal
    printf("Iterative preorder traversal:\n");
    iterative_preorder(root);
    printf("\n\n");

    // (*) Iterative postorder traversal
    printf("Iterative postorder traversal:\n");
    iterative_postorder(root);
    printf("\n\n");

    return 0;
}