Binary Tree Inorder Traversal: Recursive and Iterative Approaches with C Code

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

typedef struct TNode { int data; struct TNode* Lsubtree; struct TNode* Rsubtree; } TNode;

typedef struct Stack { int top; int capacity; TNode** array; } Stack;

TNode* createNode(int data) { TNode* newNode = (TNode*)malloc(sizeof(TNode)); newNode->data = data; newNode->Lsubtree = NULL; newNode->Rsubtree = NULL; return newNode; }

Stack* createStack(int capacity) { Stack* newStack = (Stack*)malloc(sizeof(Stack)); newStack->capacity = capacity; newStack->top = -1; newStack->array = (TNode**)malloc(capacity * sizeof(TNode*)); return newStack; }

int isFull(Stack* stack) { return stack->top == stack->capacity - 1; }

int isEmpty(Stack* stack) { return stack->top == -1; }

void push(Stack* stack, TNode* node) { if (isFull(stack)) { printf('Stack is full\n'); return; } stack->array[++stack->top] = node; }

TNode* pop(Stack* stack) { if (isEmpty(stack)) { printf('Stack is empty\n'); return NULL; } return stack->array[stack->top--]; }

void inorder1(TNode* tree) { if (tree != NULL) { inorder1(tree->Lsubtree); printf('%d ', tree->data); inorder1(tree->Rsubtree); } }

void inorder2(TNode* tree) { TNode* p = tree; Stack* stack = createStack(100); do { while (p != NULL) { push(stack, p); p = p->Lsubtree; } if (!isEmpty(stack)) { p = pop(stack); printf('%d ', p->data); p = p->Rsubtree; } } while (!isEmpty(stack) || p != NULL); }

int main() { TNode* root = createNode(1); root->Lsubtree = createNode(2); root->Rsubtree = createNode(3); root->Lsubtree->Lsubtree = createNode(4); root->Lsubtree->Rsubtree = createNode(5); root->Rsubtree->Lsubtree = createNode(6); root->Rsubtree->Rsubtree = createNode(7);

printf('Inorder traversal using recursion: ');
inorder1(root);
printf('\n');

printf('Inorder traversal using stack: ');
inorder2(root);
printf('\n');

return 0;

}