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)


-->space separated output for each node as a root.
2 2 1 1
  • 1
    $\begingroup$ 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? $\endgroup$ – dkaeae Apr 8 '19 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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.