Is there any way to find the nodes in the each subtree of each node having distance equal to height of the subtree?

We are given a tree of N nodes from 1 to N where node 1 is the root of the tree. For each node i from 1 to N, you have to find the numbers of nodes which are in the subtree of i and are at distance equal to height of subtree of i.

Distance between a & b = total number of edges in path from a to b,height of subtree = maximum distance of the root of the subtree to any node in the subtree.

I have tried to create an algorithm using dfs using adjancey list of arraylist in java but got nowhere.

example input and output: input:

first line:
4--> no of nodes---
next each line represents connection of nodes
(1 2),
(2 3),
(2 4)

output:

-->space separated output for each node as a root.
2 2 1 1
• You say you "have tried to create an algorithm". What were your ideas thus far? Where did you get stuck? Could you expound a little more on how you used DFS? – dkaeae Apr 8 at 8:53

First of all, you can notice that the nodes you are looking for are necessarly leaves of the tree (or sub-tree). What you are looking for, in each sub-tree, are the leaves that are at the largest distance from the root.

Let's call:

• $$L_k$$, the list of the furthest leaves in the sub-tree rooting at node $$k$$ (the answer to your problem).
• $$h_k$$, the distance from node $$k$$ to the furthest leaves of the sub-tree rooting at node $$k$$ (what you call height).

For all leaves, you have:

• $$h_k$$ = 0
• $$L_k$$ = [k]

For all other node, you have:

• $$h_k$$ = $$max_i (f_i) + 1$$ for each $$i$$ child of $$k$$
• $$L_k$$ = $$sum_i (L_i)$$ for each $$i$$ child of $$k$$ if $$h_k$$ == $$h_i$$+1

NB: by $$sum$$, I mean the concatenation of all the lists verificating the condition.

Globally, you can do a DFS, and once you explored all the subsequent paths from a node $$k$$, you are able to compute $$h_k$$ and $$L_k$$.