Iterative method to find ancestors of a given binary tree | C ++ program to print all ancestors of a given key ; Structure for a tree node ; A utility function to create a new tree node ; Iterative Function to print all ancestors of a given key ; Create a stack to hold ancestors ; Traverse the complete tree in postorder way till we find the key ; Traverse the left side . While traversing , push the nodes into the stack so that their right subtrees can be traversed later ; push current node ; move to next node ; If the node whose ancestors are to be printed is found , then break the while loop . ; 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 the popped node is right child of top , then remove the top as well . Left child of the top must have processed before . ; if stack is not empty then simply set the root as right child of top and start traversing right sub - tree . ; If stack is not empty , print contents of stack Here assumption is that the key is there in tree ; Driver program to test above functions ; Let us construct a binary tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; struct Node * newNode ( int data ) { struct Node * node = ( struct Node * ) malloc ( sizeof ( struct Node ) ) ; node -> data = data ; node -> left = node -> right = NULL ; return node ; } void printAncestors ( struct Node * root , int key ) { if ( root == NULL ) return ; stack < struct Node * > st ; while ( 1 ) { while ( root && root -> data != key ) { st . push ( root ) ; root = root -> left ; } if ( root && root -> data == key ) break ; if ( st . top ( ) -> right == NULL ) { root = st . top ( ) ; st . pop ( ) ; while ( ! st . empty ( ) && st . top ( ) -> right == root ) { root = st . top ( ) ; st . pop ( ) ; } } root = st . empty ( ) ? NULL : st . top ( ) -> right ; } while ( ! st . empty ( ) ) { cout << st . top ( ) -> data << " ▁ " ; st . pop ( ) ; } } int main ( ) { struct Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 7 ) ; root -> left -> left = newNode ( 3 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 8 ) ; root -> right -> right = newNode ( 9 ) ; root -> left -> left -> left = newNode ( 4 ) ; root -> left -> right -> right = newNode ( 6 ) ; root -> right -> right -> left = newNode ( 10 ) ; int key = 6 ; printAncestors ( root , key ) ; return 0 ; }