One Missing Branch

Open Data Structures gives a traversal that needs no stack and no recursion, because every node stores a parent pointer. It decides where to go next from where it just came from. Someone simplified the middle case:

void traverse2(Node *r) {
  Node *u = r, *prev = nullptr, *next;
  while (u != nullptr) {
    if (prev == u->parent) {
      if (u->left != nullptr)       next = u->left;
      else if (u->right != nullptr) next = u->right;
      else                          next = u->parent;
    } else if (prev == u->left) {
      next = u->parent;              // simplified
    } else {
      next = u->parent;
    }
    prev = u;
    u = next;
  }
}

It runs on this tree, rooted at 1:

        1
       / \
      2   3
     / \
    4   5

Which nodes does the loop never reach?

A

None. The loop still reaches every node, it just visits some of them in the wrong order.

B

3 and 5

C

5 only

D

3 only