# Iterative method to find ancestors of a given binary tree

Given a binary tree, print all the ancestors of a particular key existing in the tree without using recursion.

Here we will be discussing the implementation for the above problem.
Examples:

```Input :
1
/
2         7
/        /
3     5    8    9
/              /
4         6     10
Key = 6

Output : 5 2 1
Ancestors of 6 are 5, 2 and 1.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to use iterative postorder traversal of given binary tree.

## C++

 `// C++ program to print all ancestors of a given key ` `#include ` `using` `namespace` `std; ` ` `  `// Structure for a tree node ` `struct` `Node { ` `    ``int` `data; ` `    ``struct` `Node* left, *right; ` `}; ` ` `  `// A utility function to create a new tree node ` `struct` `Node* newNode(``int` `data) ` `{ ` `    ``struct` `Node* node = (``struct` `Node*)``malloc``(``sizeof``(``struct` `Node)); ` `    ``node->data = data; ` `    ``node->left = node->right = NULL; ` `    ``return` `node; ` `} ` ` `  `// Iterative Function to print all ancestors of a ` `// given key ` `void` `printAncestors(``struct` `Node* root, ``int` `key) ` `{ ` `    ``if` `(root == NULL) ` `        ``return``; ` ` `  `    ``// Create a stack to hold ancestors ` `    ``stack<``struct` `Node*> st; ` ` `  `    ``// 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) { ` `            ``st.push(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` `(st.top()->right == NULL) { ` `            ``root = st.top(); ` `            ``st.pop(); ` ` `  `            ``// If the popped node is right child of top, ` `            ``// then remove the top as well. Left child of ` `            ``// the top must have processed before. ` `            ``while` `(!st.empty() && st.top()->right == root) { ` `                ``root = st.top(); ` `                ``st.pop(); ` `            ``} ` `        ``} ` ` `  `        ``// if stack is not empty then simply set the root ` `        ``// as right child of top and start traversing right ` `        ``// sub-tree. ` `        ``root = st.empty() ? NULL : st.top()->right; ` `    ``} ` ` `  `    ``// If stack is not empty, print contents of stack ` `    ``// Here assumption is that the key is there in tree ` `    ``while` `(!st.empty()) { ` `        ``cout << st.top()->data << ``" "``; ` `        ``st.pop(); ` `    ``} ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``// Let us construct a binary tree ` `    ``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; ` `} `

## Java

 `// Java program to print all  ` `// ancestors of a given key  ` `import` `java.util.*; ` ` `  `class` `GfG  ` `{ ` ` `  `// Structure for a tree node  ` `static` `class` `Node ` `{  ` `    ``int` `data;  ` `    ``Node left, right;  ` `} ` ` `  `// A utility function to  ` `// create a new tree node  ` `static` `Node newNode(``int` `data)  ` `{  ` `    ``Node node = ``new` `Node();  ` `    ``node.data = data;  ` `    ``node.left = ``null``; ` `    ``node.right = ``null``;  ` `    ``return` `node;  ` `}  ` ` `  `// Iterative Function to print  ` `// all ancestors of a given key  ` `static` `void` `printAncestors(Node root, ``int` `key)  ` `{  ` `    ``if` `(root == ``null``)  ` `        ``return``;  ` ` `  `    ``// Create a stack to hold ancestors  ` `    ``Stack st = ``new` `Stack ();  ` ` `  `    ``// Traverse the complete tree in  ` `    ``// postorder way till we find the key  ` `    ``while` `(``1` `== ``1``)  ` `    ``{  ` ` `  `        ``// Traverse the left side. While  ` `        ``// traversing, push the nodes into  ` `        ``// the stack so that their right  ` `        ``// subtrees can be traversed later  ` `        ``while` `(root != ``null` `&& root.data != key)  ` `        ``{  ` `            ``st.push(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 != ``null` `&& 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` `(st.peek().right == ``null``)  ` `        ``{  ` `            ``root = st.peek();  ` `            ``st.pop();  ` ` `  `            ``// If the popped node is right child of top,  ` `            ``// then remove the top as well. Left child of  ` `            ``// the top must have processed before.  ` `            ``while` `(!st.isEmpty() && st.peek().right == root) ` `            ``{  ` `                ``root = st.peek();  ` `                ``st.pop();  ` `            ``}  ` `        ``}  ` ` `  `        ``// if stack is not empty then simply  ` `        ``// set the root as right child of  ` `        ``// top and start traversing right  ` `        ``// sub-tree.  ` `        ``root = st.isEmpty() ? ``null` `: st.peek().right;  ` `    ``}  ` ` `  `    ``// If stack is not empty, print contents of stack  ` `    ``// Here assumption is that the key is there in tree  ` `    ``while` `(!st.isEmpty()) ` `    ``{  ` `        ``System.out.print(st.peek().data + ``" "``);  ` `        ``st.pop();  ` `    ``}  ` `}  ` ` `  `// Driver code  ` `public` `static` `void` `main(String[] args)  ` `{  ` `    ``// Let us construct a binary tree  ` `    ``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);  ` `} ` `} ` ` `  `// This code is contributed  ` `// by prerna saini `

## Python3

 `# Python program to print all ancestors of a given key ` ` `  `# A class to create a new tree node  ` `class` `newNode: ` `    ``def` `__init__(``self``, data): ` `        ``self``.data ``=` `data  ` `        ``self``.left ``=` `self``.right ``=` `None` ` `  `# Iterative Function to print all ancestors of a  ` `# given key  ` `def` `printAncestors(root, key): ` `    ``if` `(root ``=``=` `None``):  ` `        ``return` ` `  `    ``# Create a stack to hold ancestors  ` `    ``st ``=` `[] ` ` `  `    ``# 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 ``and` `root.data !``=` `key):  ` `            ``st.append(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 ``and` `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` `(st[``-``1``].right ``=``=` `None``):  ` `            ``root ``=` `st[``-``1``]  ` `            ``st.pop()  ` ` `  `            ``# If the popped node is right child of top,  ` `            ``# then remove the top as well. Left child of  ` `            ``# the top must have processed before.  ` `            ``while` `(``len``(st) !``=` `0` `and` `st[``-``1``].right ``=``=` `root):  ` `                ``root ``=` `st[``-``1``]  ` `                ``st.pop() ` ` `  `        ``# if stack is not empty then simply set the root  ` `        ``# as right child of top and start traversing right  ` `        ``# sub-tree.  ` `        ``root ``=` `None` `if` `len``(st) ``=``=` `0` `else` `st[``-``1``].right ` ` `  `    ``# If stack is not empty, print contents of stack  ` `    ``# Here assumption is that the key is there in tree  ` `    ``while` `(``len``(st) !``=` `0``):  ` `        ``print``(st[``-``1``].data,end ``=` `" "``)  ` `        ``st.pop() ` ` `  `# Driver code ` `if` `__name__ ``=``=` `'__main__'``: ` ` `  `    ``# Let us construct a binary tree  ` `    ``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``)  ` ` `  `    ``key ``=` `6` `    ``printAncestors(root, key) ` `     `  `# This code is contributed by PranchalK. `

## C#

 `// C# program to print all  ` `// ancestors of a given key  ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GfG  ` `{ ` ` `  `// Structure for a tree node  ` `public` `class` `Node ` `{  ` `    ``public` `int` `data;  ` `    ``public` `Node left, right;  ` `} ` ` `  `// A utility function to  ` `// create a new tree node  ` `static` `Node newNode(``int` `data)  ` `{  ` `    ``Node node = ``new` `Node();  ` `    ``node.data = data;  ` `    ``node.left = ``null``; ` `    ``node.right = ``null``;  ` `    ``return` `node;  ` `}  ` ` `  `// Iterative Function to print  ` `// all ancestors of a given key  ` `static` `void` `printAncestors(Node root, ``int` `key)  ` `{  ` `    ``if` `(root == ``null``)  ` `        ``return``;  ` ` `  `    ``// Create a stack to hold ancestors  ` `    ``Stack st = ``new` `Stack ();  ` ` `  `    ``// Traverse the complete tree in  ` `    ``// postorder way till we find the key  ` `    ``while` `(1 == 1)  ` `    ``{  ` ` `  `        ``// Traverse the left side. While  ` `        ``// traversing, push the nodes into  ` `        ``// the stack so that their right  ` `        ``// subtrees can be traversed later  ` `        ``while` `(root != ``null` `&& root.data != key)  ` `        ``{  ` `            ``st.Push(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 != ``null` `&& 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` `(st.Peek().right == ``null``)  ` `        ``{  ` `            ``root = st.Peek();  ` `            ``st.Pop();  ` ` `  `            ``// If the popped node is right child of top,  ` `            ``// then remove the top as well. Left child of  ` `            ``// the top must have processed before.  ` `            ``while` `(st.Count != 0 && st.Peek().right == root) ` `            ``{  ` `                ``root = st.Peek();  ` `                ``st.Pop();  ` `            ``}  ` `        ``}  ` ` `  `        ``// if stack is not empty then simply  ` `        ``// set the root as right child of  ` `        ``// top and start traversing right  ` `        ``// sub-tree.  ` `        ``root = st.Count == 0 ? ``null` `: st.Peek().right;  ` `    ``}  ` ` `  `    ``// If stack is not empty, print contents of stack  ` `    ``// Here assumption is that the key is there in tree  ` `    ``while` `(st.Count != 0) ` `    ``{  ` `        ``Console.Write(st.Peek().data + ``" "``);  ` `        ``st.Pop();  ` `    ``}  ` `}  ` ` `  `// Driver code  ` `public` `static` `void` `Main(String[] args)  ` `{  ` `    ``// Let us construct a binary tree  ` `    ``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);  ` `} ` `} ` ` `  `// This code has been contributed by 29AjayKumar `

Output:

```5 2 1
```

## tags:

Stack Tree Stack Tree