Find all nodes at given distance from leaf nodes in a binary tree

Given a binary tree, write an efficient algorithm to find all nodes present at given distance from any leaf node. We need to find only those nodes that are present in root-to-leaf path for that leaf.

 

For example, consider below binary tree


       15
     /    \
    /      \
   10       20
  / \      /  \
 8   12   16  25
         /
        18

The nodes present at distance 1 from any leaf node are 10, 16, 20
The nodes present at distance 2 from any leaf node are 15, 20
The nodes present at distance 3 from any leaf node is 15

 

 
The idea is to traverse the tree in preorder fashion and use a vector to store ancestors of a current node in pre-order traversal. If we encounter a leaf node, we print the ancestor present at given distance from it. To avoid printing duplicates, we can insert the nodes into a set and print it later. Below is the C++ implementation of the idea –

 

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 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Techie
Guest
Techie

When path is passed recursively, is it passed by value or by reference?