C++-এ রিকার্সন ছাড়া বাইনারি ট্রি নোডের পূর্বপুরুষ প্রিন্ট করুন

স্ট্যাক ব্যবহার করে পোস্ট-অর্ডার ট্রাভার্সাল করা হয়। রুট থেকে টার্গেট নোড পর্যন্ত পথে পড়া নোডগুলো স্ট্যাকে রাখা হয় এবং শেষে স্ট্যাকের কন্টেন্ট প্রিন্ট করা হয়।

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

struct Node {
    int data;
    struct Node *left, *right;
};

struct Stack {
    int size;
    int top;
    struct Node** array;
};

struct Node* insertNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

struct Stack* createStack(int size) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->size = size;
    stack->top = -1;
    stack->array = (struct Node**)malloc(stack->size * sizeof(struct Node*));
    return stack;
}

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

void push(struct Stack* stack, struct Node* node) {
    if (isFull(stack)) return;
    stack->array[++stack->top] = node;
}

struct Node* pop(struct Stack* stack) {
    if (isEmpty(stack)) return NULL;
    return stack->array[stack->top--];
}

struct Node* peek(struct Stack* stack) {
    if (isEmpty(stack)) return NULL;
    return stack->array[stack->top];
}

void AncestorNodes(struct Node *root, int key) {
    if (root == NULL) return;
    struct Stack* stack = createStack(MAX_SIZE);
    while (1) {
        while (root && root->data != key) {
            push(stack, root);
            root = root->left;
        }
        if (root && root->data == key) break;
        if (peek(stack)->right == NULL) {
            root = pop(stack);
            while (!isEmpty(stack) && peek(stack)->right == root)
                root = pop(stack);
        }
        root = isEmpty(stack) ? NULL : peek(stack)->right;
    }
    while (!isEmpty(stack))
        printf("%d ", pop(stack)->data);
}

int main() {
    struct Node* root = insertNode(15);
    root->left = insertNode(10);
    root->right = insertNode(25);
    root->left->left = insertNode(5);
    root->left->right = insertNode(12);
    root->right->left = insertNode(20);
    root->right->right = insertNode(27);
    root->left->left->left = insertNode(1);
    root->left->right->right = insertNode(14);
    root->right->right->left = insertNode(17);
    printf("The ancestors of the given node are: ");
    AncestorNodes(root, 17);
    getchar();
    return 0;
}

The ancestors of the given node are: 27 25 15