Print ancestors of a given binary tree node

Print ancestors of a given binary tree node without recursion | GeeksforGeeks
Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.

https://www.geeksforgeeks.org/print-ancestors-of-a-given-node-in-binary-tree/

Thinking of solution??Think Recursively.This problem can be easily solved using recursion. We start from the root of the tree and keep going down the tree. When we reach the node with given value we return true.if a node contains the given node in left or right subtree we print it and return true to it’s parent till we reach root.    boolean printAncestors(Node node, int target) 

    {

         /* base cases */

        if (node == null)

            return false;

   

        if (node.data == target)

            return true;

   

        /* If target is present in either left or right subtree 

           of this node, then print this node */

        if (printAncestors(node.left, target)

                || printAncestors(node.right, target)) 

        {

            System.out.print(node.data + " ");

            return true;

        }

   

        /* Else return false */

        return false;

    }

How to get all ancestors in stack when we reach the given node? We can traverse all nodes in Postorder way. 
If we take a closer look at the recursive postorder traversal, we can easily observe that, when recursive function is called for a node, the recursion call stack contains ancestors of the node. So idea is do iterative Postorder traversal and stop the traversal when we reach the desired node.

void printAncestors(struct Node *root, int key)

{

    if (root == NULL) return;

    // Create a stack to hold ancestors

    struct Stack* stack = createStack(MAX_SIZE);

    // Traverse the complete tree in postorder way till we find the key

    while (1)

    {

        // Traverse the left side. While traversing, push the nodes into

        // the stack so that their right subtrees can be traversed later

        while (root && root->data != key)

        {

            push(stack, root);   // push current node

            root = root->left;  // move to next node

        }

        // If the node whose ancestors are to be printed is found,

        // then break the while loop.

        if (root && root->data == key)

            break;

        // Check if right sub-tree exists for the node at top

        // If not then pop that node because we don't need this

        // node any more.

        if (peek(stack)->right == NULL)

        {

            root = pop(stack);

            // If the popped node is right child of top, then remove the top

            // as well. Left child of the top must have processed before.

            // Consider the following tree for example and key = 3.  If we

            // remove the following loop, the program will go in an

            // infinite loop after reaching 5.

            //          1

            //        /   \

            //       2     3

            //         \

            //           4

            //             \

            //              5

            while (!isEmpty(stack) && peek(stack)->right == root)

               root = pop(stack);

        }

        // if stack is not empty then simply set the root as right child

        // of top and start traversing right sub-tree.

        root = isEmpty(stack)? NULL: peek(stack)->right;

    }

    // If stack is not empty, print contents of stack

    // Here assumption is that the key is there in tree

    while (!isEmpty(stack))

        printf("%d ", pop(stack)->data);

}

Read full article from Print ancestors of a given binary tree node without recursion | GeeksforGeeks