Given a binary tree, find all ancestors of given node in it.

For example, consider below binary tree

Ancestor of node 9 are 7, 3 and 1

Ancestor of node 6 are 3 and 1

Ancestor of node 5 are 2 and 1

. . .

The idea is to traverse the tree in postorder fashion and search for given node in the tree. If the node is found, we return true from the function. So for any node, if the given node is found in either its left subtree or its right subtree, then the current node is an ancestor of it.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Recursive function to print all ancestors of given node in a // binary tree. The function returns true if node is found in // subtree rooted at given root node bool printAncestors(Node *root, int node) { // base case if (root == nullptr) return false; // return true if given node is found if (root->data == node) return true; // search node in left subtree bool left = printAncestors(root->left, node); // search node in right subtree if left subtree returns false bool right = false; if (!left) right = printAncestors(root->right, node); // if given node is found in either left or right subtree, // current node is an ancestor of given node if (left || right) cout << root->data << " "; // return true if node is found return left || right; } |

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

#### Iterative solution –

The idea is to main a map to store parent node information of all nodes present in the tree. Then we do a iterative pre-order traversal of the tree, and set parent pointer of each node. Finally, we print ancestors of given key by using parent map.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to print root to leaf paths without using recursion void printTopToBottomPath(unordered_map<int, int> parent, int key) { while (key = parent[key]) cout << key << " "; cout << endl; } // iterative function to set parent nodes for all nodes of binary tree // in given map. The function is similar to iterative pre-order traversal void setParent(Node* root, unordered_map<int, int> &parent) { // create an empty stack and push root node to it stack<Node*> stack; stack.push(root); // run till stack is not empty while (!stack.empty()) { // Pop the top item from stack Node* curr = stack.top(); stack.pop(); // push its right child to stack and set its parent in the map. // Since right child is pushed first, left child will be // processed before if (curr->right) { parent[curr->right->data] = curr->data; stack.push(curr->right); } // push its left child to stack and set its parent in the map if (curr->left) { parent[curr->left->data] = curr->data; stack.push(curr->left); } } } // Iterative function to print all ancestors of given node in binary tree void printAncestors(Node* root, int node) { // Base Case if (root == nullptr) return; // create a empty map to store parent pointers of binary tree nodes unordered_map<int, int> parent; // set parent of root node as null parent[root->data] = 0; // set parent nodes for all nodes of binary tree setParent(root, parent); // print ancestors of given node using parent map printTopToBottomPath(parent, node); } |

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

nicely done..

In recursive case, may be we could return if left returns true and not look in right subtree.

Thanks Arun for the optimization.. We have updated the code.

why is 6 not a ancestor of the node 9..?

Thanks Kishore for sharing your concerns. Please note that node 6 doesn’t lie on path from root node to node 9. Hence, node 6 is not an ancestor of node 9. Hope you’re clear now.

Oh, I see, the node is like 6 -> 8 and 7 -> 9….. the diagram is not clear at the end, thanks for clearing it.

how can we return ancestor nodes as linked list?

errr.. simple solution is to just do a binary search for the given node and print the values along the path ?!!

You can’t do binary search on a binary tree. If you mean perform standard search operation, please note that the tree in question is binary tree, and not a binary search tree.