Find ancestors of given node in a Binary Tree

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


 

For example, consider below binary tree

 
Root To Leaf Paths

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 –
 

Download   Run Complete Code

 
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 –
 

Download   Run Complete Code

 
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.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Top Coder
Guest

nicely done..

Arun
Guest

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

Kishore
Guest

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

Manish Sakariya
Guest

how can we return ancestor nodes as linked list?

Shishir Ramesha
Guest

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

Anon
Guest

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.