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.