recursion - 二分探索木の高さを再帰的に見つける - どのように機能しますか?

Question

二分探索木の高さを求める問題の一般的な解決策は、次のようになります。

private int getHeight(Node<T> ptr, String typeOfCall)
{
    if (ptr == null)
        return -1;

    int leftHeight = -1;
    int rightHeight = -1;

    System.out.println(input);
    System.out.println("Node value: " + ptr.el);

    if (ptr != null)
        leftHeight = getHeight(ptr.left, "leftHeight Call");
    if (ptr != null)
        rightHeight = getHeight(ptr.right, "rightHeight Call");

    if(leftHeight > rightHeight)
        return leftHeight + 1;
    else
        return rightHeight + 1;

}

ご覧のとおり、この方法がどのように機能するかを理解しようとするために、いくつかのコード行を追加しました...

以下の BST を例にとります。

                             99
                            /  \
                          50    100
                         /  \
                       49    55
                      /        \
                     48         60
                    /             \
                   47              70
                                     \ 
                                      80

追加したコードで得られる出力は次のとおりです。

first
Node value: 99
leftHeight Call
Node value: 50
leftHeight Call
Node value: 49
leftHeight Call
Node value: 48
leftHeight Call
Node value: 47
rightHeight Call
Node value: 55
rightHeight Call  
Node value: 60
rightHeight Call
Node value: 70
rightHeight Call
Node value: 80
rightHeight Call
Node value: 100
height: 5

私の質問は次のとおりです: 関数は、値 47 のリーフ ノードから値 55 のノードに移動し、そこから可能な限り下に移動する必要があることをどのように認識しますか? つまり、現在ptrが値47のリーフノードを指しているときに、ptr.right.element = 55はどのようになりますか? リーフノードにあるため、ptr.rightはnullになると思いましたか? また、値 80 を持つリーフ ノードが検出されると、関数は右側のサブツリーに移動します。これを行うことをどのように知っていますか？

どんな説明でも大歓迎です！ここに含まれる再帰に関する何かが、おそらく私の混乱の原因だと思います。この機能はどのように機能しますか? ありがとう！

編集Oli が提案した後、再帰関数呼び出しの下にいくつかの print ステートメントを追加しました。

            private int getHeight(Node<T> ptr, String typeOfCall)
    if (ptr == null)
        return -1;

    int leftHeight = -1;
    int rightHeight = -1;

    System.out.println("Before: " + input);
    System.out.println("Before: " + ptr.el);

    if (ptr != null)
        leftHeight = getHeight(ptr.left, "leftHeight Call");
    if (ptr != null)
        rightHeight = getHeight(ptr.right, "rightHeight Call");

    System.out.println("After Recursive: " + input);
    System.out.println("After Recursive: " + ptr.el);

    if(leftHeight > rightHeight)
        return leftHeight + 1;
    else
        return rightHeight + 1;
            }

出力：

Before: first
Before: 99
Before: leftHeight Call
Before: 50
Before: leftHeight Call
Before: 49
Before: leftHeight Call
Before: 48
Before: leftHeight Call
Before: 47
After Recursive: leftHeight Call
After Recursive: 47
After Recursive: leftHeight Call
After Recursive: 48
After Recursive: leftHeight Call
After Recursive: 49
Before: rightHeight Call
Before: 55
Before: rightHeight Call
Before: 60
Before: rightHeight Call
Before: 70
Before: rightHeight Call
Before: 80  
After Recursive: rightHeight Call
After Recursive: 80
After Recursive: rightHeight Call
After Recursive: 70
After Recursive: rightHeight Call
After Recursive: 60
After Recursive: rightHeight Call
After Recursive: 55
After Recursive: leftHeight Call 
After Recursive: 50
Before: rightHeight Call
Before: 100
After Recursive: rightHeight Call
Below Recursive: 100
Below Recursive: first
Below Recursive: 99

これは、ここで使用されている再帰の巻き戻しと、この関数が全体としてどのように機能するかを理解するのに非常に役立ちます。