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.

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 –

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 |
// 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

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