Iterative method to find ancestors of a given binary tree | Java 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 code ; Let us construct a binary tree
import java . util . * ; class GfG { static class Node { int data ; Node left , right ; } static Node newNode ( int data ) { Node node = new Node ( ) ; node . data = data ; node . left = null ; node . right = null ; return node ; } static void printAncestors ( Node root , int key ) { if ( root == null ) return ; Stack < Node > st = new Stack < Node > ( ) ; while ( 1 == 1 ) { while ( root != null && root . data != key ) { st . push ( root ) ; root = root . left ; } if ( root != null && root . data == key ) break ; if ( st . peek ( ) . right == null ) { root = st . peek ( ) ; st . pop ( ) ; while ( ! st . isEmpty ( ) && st . peek ( ) . right == root ) { root = st . peek ( ) ; st . pop ( ) ; } } root = st . isEmpty ( ) ? null : st . peek ( ) . right ; } while ( ! st . isEmpty ( ) ) { System . out . print ( st . peek ( ) . data + " ▁ " ) ; st . pop ( ) ; } } public static void main ( String [ ] args ) { 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 ) ; } }