Dsa
Trees
Medium
The Depth Echo
In a rooted tree (root is node 0), an 'Echo' at distance D from node U is any descendant of U that is exactly D edges away. Given a tree and an integer D, calculate the total number of such (U, V) pairs in the tree where V is an Echo of U at distance D.
Input Format:
- Line 1: N and D.
- Next N-1 lines: Two integers u and v (where u is the parent of v).
Output Format:
- A single integer representing the total count of pairs.
Example:
Input:
4 1
0 1
0 2
1 3
Output:
3
Explanation: Pairs at distance 1: (0,1), (0,2), (1,3). Total 3.
Key concepts
treebreadth-first searchlevel order
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now