Implementation of a distance matrix of a binary tree that is given in the adjacency-list representation
- by Denise Giubilei
Given this problem I need an O(n²) implementation of this algorithm:
"Let v be an arbitrary leaf in a binary tree T, and w be the only vertex connected to v. If we remove v, we are left with a smaller tree T'. The distance between v and any vertex u in T' is 1 plus the distance between w and u."
This is a problem and solution of a Manber's exercise (Exercise 5.12 from U. Manber, Algorithms: A Creative Approach, Addison-Wesley (1989).).
The thing is that I can't deal properly with the adjacency-list representation so that the implementation of this algorithm results in a real O(n²) complexity.
Any ideas of how the implementation should be?
Thanks.