Hello Sir, I understood the problem very well but the solution you explained wasn’t very clear. It was fast and wasn’t approached bit by bi and many tings came all at once at some part. Please explain it clearly. Thank You!
Solution of the problem not clear
There are two types of nodes to be considered.
1) Nodes in the subtree rooted with target node. For example if the target node is 8 and k is 2, then such nodes are 10 and 14.
2) Other nodes, may be an ancestor of target, or a node in some other subtree. For target node 8 and k is 2, the node 22 comes in this category.
Finding the first type of nodes is easy to implement. Just traverse subtrees rooted with the target node and decrement k in recursive call. When the k becomes 0, print the node currently being traversed (See this for more details). Here we call the function as printkdistanceNodeDown() .
How to find nodes of second type? For the output nodes not lying in the subtree with the target node as the root, we must go through all ancestors. For every ancestor, we find its distance from target node, let the distance be d, now we go to other subtree (if target was found in left subtree, then we go to right subtree and vice versa) of the ancestor and find all nodes at k-d distance from the ancestor.
1 Like
Hello Ma’am,
Thanks. The solution is quite clear now. I still want to discuss the approach for the second part:
Like, for ancestors, we can start from the root node and run the algorithm for every possible ancestor of that node, right?
yes
just the net distance will be 1 less
since we have already covered one node
1 Like
Oh, okay okay!
I got that bit. I’ll try and implement it and ask my doubt in the code if I get any!
Thanks a lot!
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
Hello @chhavibansal
I’m still on my trees section, and I’ll attempt the problem in a day or two after studying the concepts. I’ll post my doubt if any or rate the experience then!
Thank you
1 Like