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
kishore
Guest
kishore

Amazing post, I switched my language to cpp from java, just because this site has so much of the problems in cpp. and it’s really worth it.

Techie
Guest
Techie

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

Ankit
Guest
Ankit

passed by value