binary-search-tree - BST [宿題] 反復トラバーサルのこの方法はどのように機能しますか?

Question

ここでは、Pat Morin による無料の書籍 Open Data Structures (in Java) の例を使用しています。ツリートラバーサルで何が起こっているかの概念を理解していると思います（左に移動できなくなるまで左に進み、次に右に移動してから戻る.

ただし、以下のコードには少し困惑しています。次のような構造でブランチを変更することをどのように正確に認識しますか。

  r(oot)
  |
 -  -
|    |
a    b
   |  |
   c  d

void traverse2() {
     Node u = r, prev = nil, next;
     while (u != nil) {
       if (prev == u.parent) {
         if (u.left != nil) next = u.left;
         else if (u.right != nil) next = u.right;
         else next = u.parent;
       } else if (prev == u.left) {
         if (u.right != nil) next = u.right;
         else next = u.parent;
       } else {
         next = u.parent;
       }
       prev = u;
       u = next;
} }

ルートに何もなくても、自動的に親に移動することがわかりますか?