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.

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 implementation of the idea –

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to check if given node is a leaf node or not bool isLeaf(Node* node) { return (node->left == nullptr && node->right == nullptr); } // Recursive function to find all nodes at given distance from leaf nodes void leafNodeDistance(Node* node, vector<Node*> path, set<Node*> &set, int dist) { // base case: empty tree if (node == nullptr) return; // if a leaf node is found, insert the node at distance 'dist' from // leaf node into the set if (isLeaf(node) && path.size() >= dist) { set.insert(path.at(path.size() - dist)); return; } // include current node into current path path.push_back(node); // recurse for left and right subtree leafNodeDistance(node->left, path, set, dist); leafNodeDistance(node->right, path, set, dist); } // find all distinct nodes at given distance from leaf nodes void leafNodeDistance(Node* node, int dist) { // vector to store root to leaf path vector<Node*> path; // create an empty set to store distinct nodes at given // distance from leaf nodes set<Node*> set; // find all nodes leafNodeDistance(node, path, set, dist); // print output for (Node* node: set) cout << node->data << " "; } |

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 🙂

## Leave a Reply

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