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


          1
        /   \
       /     \
      2       3
     / \     / \
    4   5   6   7
           /     \
          8       9


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 ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


    

  • Top Coder

    nicely done..