Как узнать расстояние между вершинами в дереве?

Question

[sashx]

Друзья, здравствуйте! Не могу догадаться, как используя DFS я могу узнать расстояния между двумя введёнными вершинами в дереве? (Дерево неориентированное и не взвешенное)

Для примера из картинки:
Расстояние между 0 и 15 равно трём.

Answer 1

[Alexandroppolus]

Для такого дела BFS удобнее.
Складывая узлы в очередь, просто добавляй туда же расстояние (если у текущего обрабатываемого узла расстояние равно N, то попавшие в очередь чилды получают N+1)

Answer 2

[Wataru]

Ваше дерево должно быть неориентированным. Просто список соседних вершин для каждой. А там запускайте от одной вершины DFS или BFS, который считает расстояние и выводит его, если дошли до второй вершины.