Implement Non-Recursive Inorder Traversal for LeetCode Problem #94 to Avoid Stack Overflow

The current implementation of bst_inorder_traversal.c uses a recursive method for inorder traversal, which may lead to a stack overflow in cases of deep recursion. To mitigate this issue, it is recommended to use an iterative approach with an explicit stack. This prevents excessive stack usage and enhances the program's robustness. Below is the improved code:

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct Stack {
    struct TreeNode* node;
    struct Stack* next;
};

void push(struct Stack** stack, struct TreeNode* node) {
    struct Stack* new_node = (struct Stack*)malloc(sizeof(struct Stack));
    if (new_node == NULL) {
        exit(1);
    }
    new_node->node = node;
    new_node->next = *stack;
    *stack = new_node;
}

struct TreeNode* pop(struct Stack** stack) {
    if (*stack == NULL) {
        return NULL;
    }
    struct Stack* top = *stack;
    struct TreeNode* node = top->node;
    *stack = top->next;
    free(top);
    return node;
}

int isEmpty(struct Stack* stack) {
    return stack == NULL;
}

void inorderTraversal(struct TreeNode* root) {
    struct Stack* stack = NULL;
    struct TreeNode* current = root;

    while (current != NULL || !isEmpty(stack)) {
        while (current != NULL) {
            push(&stack, current);
            current = current->left;
        }
        current = pop(&stack);
        printf("%d ", current->val);
        current = current->right;
    }
}

This approach improves memory management and ensures the traversal can handle deeper trees without crashing.

begeekmyfriend / leetcode

Implement Non-Recursive Inorder Traversal for LeetCode Problem #94 to Avoid Stack Overflow #29