Как найти глубину/уровень узла в небиновом дереве?

Question

У меня есть древовидная структура, где каждый узел может иметь практически неограниченные дети, он моделирует комментарии для блога.

Я пытаюсь выяснить, учитывая идентификатор конкретного комментария, на какой глубине/уровне этот комментарий лежит в дереве.

Я следовал this guide that explains it for binary trees, но при адаптации его к недвоичным деревьям у меня проблемы.

Вот моя попытка до сих пор (в Swift):

func commentLevelRecursive(comment: Comment, commentID: String, currentLevel: Int) -> Int { 
    if comment.identifier == commentID { 
     return currentLevel 
    } 

    var newLevel = currentLevel 

    for reply in comment.replies { 
     newLevel = commentLevelRecursive(reply, commentID: commentID, currentLevel: currentLevel + 1) 
    } 

    return newLevel 
} 

Но это всегда казалось бы, возвращает 1. Я думаю, что это происходит потому, что newLevel всегда получает увеличилось с 0 до 1, то возвращается.

Может ли кто-нибудь дать мне некоторое представление о том, где я ошибаюсь?

Answer 1

Двоичное дерево - особый случай, когда каждый узел имеет только двух детей. Метод, используемый для определения уровня узла, может быть распространен на общее дерево.

Идея та же:

level(P) = max(level(C) for each child node C of P)+1 

Answer 2

int MaxDepth(int x,int parent){ 
    int mx = 0; 
    for(int i = 0;i < graph[x].size();i++) 
     if(graph[x][i]!=parent){ 
      mx = max(MaxDepth(graph[x][i],x),mx); 
     } 
     return mx + 1; 
}