tree print

tree.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_SIZE 15
typedef struct
{
    int data[MAX_SIZE];
    int top;
} stack_t;
void initialize_stack(stack_t *s);
int is_empty(stack_t *s);
void push(stack_t *s, int item);
int pop(stack_t *s);
void inorder_traversal_iterative(const int *tree_array, int size);
void postorder_traversal_iterative(const int *tree_array, int size);
void print_tree_structure(const int *tree_array, int size);
int get_tree_height(int size);
void initialize_stack(stack_t *s)
{
    s->top = -1;
}
int is_empty(stack_t *s)
{
    return s->top == -1;
}
void push(stack_t *s, int item)
{
    if (s->top >= MAX_SIZE - 1)
    {
        printf("error: stack overflow\n");
        return;
    }
    s->data[++s->top] = item;
}
int pop(stack_t *s)
{
    if (is_empty(s))
    {
        printf("error: stack underflow\n");
        return -1;
    }
    return s->data[s->top--];
}
int get_tree_height(int size)
{
    if (size == 0)
        return 0;
    return (int)ceil(log2(size + 1));
}

void print_tree_structure(const int *tree_array, int size) {
    if (size == 0) {
        printf("the tree is empty.\n");
        return;
    }

    printf("visual representation (level-by-level):\n");
    
    int height = get_tree_height(size);
    int node_width = 3; // Space for "%3d" output
    int current_index = 0;

    for (int level = 0; current_index < size; ++level) {
        int nodes_at_level = 1 << level; // 2^level
        
        // Total unit space allocated for a node at this level
        // (Scales up for higher levels to create the pyramid shape)
        int total_unit_space = (1 << (height - level)) * (node_width + 1);
        
        // Calculate leading space before the first node
        int leading_space = total_unit_space / 2;
        
        // Print leading spaces
        for (int i = 0; i < leading_space; ++i) {
            printf(" ");
        }

        // Print nodes for the current level
        int level_start_index = current_index;
        for (int i = 0; i < nodes_at_level && current_index < size; ++i) {
            printf("%*d", node_width, tree_array[current_index]);
            
            // Print spacing between nodes
            if (i < nodes_at_level - 1 && current_index + 1 < size) {
                // Inter-node space is the full unit space
                for (int j = 0; j < total_unit_space; ++j) {
                    printf(" ");
                }
            }
            current_index++;
        }
        printf("\n");
        
        // Print connection lines (/) and (\) to show hierarchy
        if (level < height - 1) {
            
            // Print leading spaces for the lines
            for (int i = 0; i < leading_space - 1; ++i) {
                printf(" ");
            }

            for (int i = level_start_index; i < current_index && i < size; ++i) {
                
                // Print '/' for left child
                if (2 * i + 1 < size) {
                    //printf("/");
                } else {
                    printf(" ");
                }
                
                // Space between '/' and '\'
                // This space represents the center of the structure
                for (int j = 0; j < total_unit_space - 1; ++j) {
                    printf(" ");
                }

                // Print '\' for right child
                if (2 * i + 2 < size) {
                    //printf("\\");
                } else {
                    printf(" ");
                }

                // Space after node line pair to align with the next parent node
                for (int j = 0; j < total_unit_space + 1; ++j) {
                     printf(" ");
                }
            }
            printf("\n");
        }
    }
}


void inorder_traversal_iterative(const int *tree_array, int size)
{
    if (size == 0)
        return;
    stack_t stack;
    initialize_stack(&stack);
    int current_index = 0;
    printf("inorder traversal (iterative): ");
    while (current_index < size || !is_empty(&stack))
    {
        while (current_index < size)
        {
            push(&stack, current_index);
            current_index = 2 * current_index + 1;
        }
        int node_index = pop(&stack);
        printf("%d ", tree_array[node_index]);
        current_index = 2 * node_index + 2;
    }
    printf("\n");
}
void postorder_traversal_iterative(const int *tree_array, int size)
{
    if (size == 0)
        return;
    stack_t s1, s2; 
    initialize_stack(&s1);
    initialize_stack(&s2);
    push(&s1, 0);
    while (!is_empty(&s1))
    {
        int node_index = pop(&s1);
        push(&s2, node_index);
        int left_child = 2 * node_index + 1;
        if (left_child < size)
        {
            push(&s1, left_child);
        }
        int right_child = 2 * node_index + 2;
        if (right_child < size)
        {
            push(&s1, right_child);
        }
    }
    printf("postorder traversal (iterative): ");
    while (!is_empty(&s2))
    {
        printf("%d ", tree_array[pop(&s2)]);
    }
    printf("\n");
}
int main()
{
    int n;
    printf("enter the number of integers (n, max %d): ", MAX_SIZE);
    if (scanf("%d", &n) != 1 || n < 0 || n > MAX_SIZE)
    {
        printf("invalid input for n. exiting.\n");
        return 1;
    }
    int *tree_array = (int *)malloc(n * sizeof(int));
    if (tree_array == NULL)
    {
        printf("memory allocation failed. exiting.\n");
        return 1;
    }
    printf("enter %d integers to form the complete binary tree:\n", n);
    for (int i = 0; i < n; i++)
    {
        if (scanf("%d", &tree_array[i]) != 1)
        {
            printf("invalid input. exiting.\n");
            free(tree_array);
            return 1;
        }
    }
    printf("\n--- complete binary tree array representation ---\n");
    printf("array: [");
    for (int i = 0; i < n; i++)
    {
        printf("%d%s", tree_array[i], (i == n - 1 ? "" : ", "));
    }
    printf("]\n\n");
    print_tree_structure(tree_array, n);
    printf("\n");
    inorder_traversal_iterative(tree_array, n);
    postorder_traversal_iterative(tree_array, n);
    free(tree_array);
    return 0;
}