Question

link

Find the nodes at d distance from a certain node in a Binary Tree

Solution

There are two types of nodes to be considered:

1. Nodes in the subtree rooted of the target node.
2. Other nodes, may be an ancestor of target, or a node in some other subtree.

The details of find these nodes:

1. Find the nodes which can be reached in k hops from the given node.

2. 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.

Implementation:

1. Start from root, store all nodes in a queue of maximum size k till you reach the given node.

2. Call FindNodesAtDistance() on the nodes from the queue to get all the nodes distance k -i from the node.