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?
Sign in to answer questions and track your progress
Sign In