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

[cw4real]

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]

That's fine to me. But the recursive method is generally recommended in programming especially in tree structures for its simplicity and clean coding. Literally we do not need to worry about the stack overflow issue in recursive method because in modern C runtime, the allocation size of stack frame of function will be large enough for storage when the programming is running. And we can see recursive method everywhere in Leetcode problems no matter how complicated the test cases are. So just go ahead and use it as you like.