Iterative method to find ancestors of a given binary tree | A class 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
class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def printAncestors ( root , key ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT st = [ ] NEW_LINE while ( 1 ) : NEW_LINE INDENT while ( root and root . data != key ) : NEW_LINE INDENT st . append ( root ) NEW_LINE root = root . left NEW_LINE DEDENT if ( root and root . data == key ) : NEW_LINE INDENT break NEW_LINE DEDENT if ( st [ - 1 ] . right == None ) : NEW_LINE INDENT root = st [ - 1 ] NEW_LINE st . pop ( ) NEW_LINE while ( len ( st ) != 0 and st [ - 1 ] . right == root ) : NEW_LINE INDENT root = st [ - 1 ] NEW_LINE st . pop ( ) NEW_LINE DEDENT DEDENT root = None if len ( st ) == 0 else st [ - 1 ] . right NEW_LINE DEDENT while ( len ( st ) != 0 ) : NEW_LINE INDENT print ( st [ - 1 ] . data , end = " ▁ " ) NEW_LINE st . pop ( ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 7 ) NEW_LINE root . left . left = newNode ( 3 ) NEW_LINE root . left . right = newNode ( 5 ) NEW_LINE root . right . left = newNode ( 8 ) NEW_LINE root . right . right = newNode ( 9 ) NEW_LINE root . left . left . left = newNode ( 4 ) NEW_LINE root . left . right . right = newNode ( 6 ) NEW_LINE root . right . right . left = newNode ( 10 ) NEW_LINE key = 6 NEW_LINE printAncestors ( root , key ) NEW_LINE DEDENT