The content of this video is not well explained

#1

The content of this video lecture Binary Tree-Nodes at Distance K from Given Node is not well explained UNLIKE other videos. Kindly help me with understanding this. I have not at all understood this topic.
Thank you!

#2

hello @rkganeshan2010

Intuition

From root , say the target node is at depth 3 in the left branch. It means that any nodes that are distance K - 3 in the right branch should be added to the answer.

Algorithm

Traverse every node with a depth first search dfs . We’ll add all nodes x to the answer such that node is the node on the path from x to target that is closest to the root .

To help us, dfs(node) will return the distance from node to the target . Then, there are 4 cases:

  • If node == target , then we should add nodes that are distance K in the subtree rooted at target .
  • If target is in the left branch of node , say at distance L+1 , then we should look for nodes that are distance K - L - 1 in the right branch.
  • If target is in the right branch of node , the algorithm proceeds similarly.
  • If target isn’t in either branch of node , then we stop.

In the above algorithm, we make use of the auxillary function subtree_add(node, dist) which adds the nodes in the subtree rooted at node that are distance K - dist from the given node .

image

image

#3

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.