Find the nodes at d distance from a certain node in a Binary Tree
There are two types of nodes to be considered:
- Nodes in the subtree rooted of the target node.
- Other nodes, may be an ancestor of target, or a node in some other subtree.
The details of find these nodes:
Find the nodes which can be reached in k hops from the given node.
Second part we look at those nodes on the upper part of the tree. The parent of the given node is 1 hop away. Hence in the other child subtree of the parent, we find nodes with k-1 hops.
Similarly the grand parent of B, we find nodes with k - 2 distance.
Start from root, store all nodes in a queue of maximum size k till you reach the given node.
Call FindNodesAtDistance() on the nodes from the queue to get all the nodes distance k -i from the node.