Print ancestors of a given binary tree node without recursion in C++

In this tutorial, we will see Print ancestors of a given binary tree node without recursion in C ++. In this type of problem we will have a binary tree and a key value of the node of which we have to find ancestors.

Example:-

            1
         /     \
       2         3
     /   \     /   
    4     5    6    

Key value      Ancestors 

1                        –

2                       1

3                       1

4                       2 1

5                       2 1

6                       3 1

You can solve this problem either by recursion or iteration. In this article we are going to solve this problem by iteratively. We will use one stack, TreeNode and key value to solve this problem. We will do the postorder traversal of tree in an iterative way and store the TreeNode in the stack. And once we reach the required value we will break the loop and print the stack of TreeNode.

C++ program to print ancestors of a given binary tree node without recursion

Function to print ancestors of a given node

void ancestors(TreeNode *root, int key) 
{ 
    if (root == NULL) return; 
  
    stack<TreeNode*> s
    while (TRUE) 
    { 
        while (root!=NULL and root->data != key) 
        { 
            s.push(root);  
            root = root->left;   
        } 
        if (root!=NULL and root->data == key) 
            break; 
        if (s.top()->right == NULL) 
        { 
            root = s.pop(); 
            while (!s.empty() && s.top()->right == root) 
               root = pop(stack); 
        }  
        root = s.empty()? NULL: s.top()->right; 
    } 
    while (!s.empty()) 
        {
           cout<<s.top()->data;
           s.pop();
        } 
}

Input:-

6

Output:-

3 1

This is a function in which we will give root and key values of the tree and it will print the required output. We are first creating a stack of TreeNode and then are applying while loop for postorder traversal of the tree and pushing the node in the stack. Once we get the required node the loop will stop and then we will print the stack using a while loop.

I hope you enjoyed the article. Thank you!

Leave a Reply

Your email address will not be published. Required fields are marked *