Hello, I have one doubt in the approach discussed in this video, that why they are considering only two cases, one either printing ancestor node or printing node in the right(if target node is at left) side and vice versa. It might happen that the target node is at more than k distance away from it ancestor and in that case neither of the cases will work.
Not considering one case why?
For this problem we can encounter two kinds of nodes .
- Nodes in the subtree rooted with target node.
- Other nodes, may be an ancestor of target, or a node in some other subtree.
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 .
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.
these are the only 2 required in the question https://hack.codingblocks.com/app/contests/718/350/problem
Hey Abha,
Thanks a lot for your reply,
Actually I am not asking the approach, what my doubt is what if the ancestor node is more than k distance away from target node or when you are printing k level in the right subtree (when u have your target node in left subtree) your k-2-DL is negative. then how we are accounting such cases …
Hello @great whenever the k will be come less than zero we will handle that case by checking and return at that point only.
