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

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

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

newest oldest most voted
Notify of

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.


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


passed by value