Trouver la profondeur totale de chaque nœud dans un arbre de recherche binaire de manière récursive ?

Question

Je suis confronté à ce problème depuis un certain temps et je n'arrive pas à en comprendre la logique. Disons que j'ai un arbre binaire qui ressemble à ce qui suit :

        8                    1 * 0 =  0
      /   \
     4    12                 2 * 1 =  2
    / \   / \
   2   6 10 14               4 * 2 =  8
                                    ----
                                     10

Je veux trouver la profondeur de chaque nœud et additionner ces nombres pour obtenir un total. Le code que j'ai actuellement ressemble à ceci :

private int totalDepth(Node node, int depth) 
{
    if(node == null) 
    {
        return 0;
    }

    return totalDepth(node.left, depth + 1) + totalDepth(node.right, depth + 1);
}

Je pensais que cela ajouterait récursivement un à chaque niveau plus profond pour le côté gauche de l'arbre (8 -> 4 -> 2) avant de parcourir le côté droit, mais cela ne fonctionne pas tout à fait.

J'ai modifié cette méthode de plusieurs façons, mais je n'arrive pas à trouver ce qui me manque. Toute aide serait grandement appréciée.

Answer 1

Vous y êtes presque : vous avez additionné les résultats des sous-arbres de gauche et de droite, mais vous avez oublié d'ajouter le résultat du nœud lui-même :

return depth                              // myself
     + totalDepth(node.left, depth + 1)   // my left subtree
     + totalDepth(node.right, depth + 1); // my right subtree

Answer 2

public virtual int GetLevelById(int id)
        {
            int i = GetParentById(id);
            if (i == 0)
                return 1;
            else
                return (1 + GetLevelById(i));
        }