That case is easily manageable: you cannot insert/appendNode that has non-null parent. So you need to remove that node from its former parent first. Problem is

That case is easily manageable: you cannot insert/appendNode that has non-null parent. So you need to remove that node from its former parent first. Problem is that their solution by design contains loops. So on each tree traversal iteration you will need to access parent: Node* get_next_node(Node* that) { that = that->next; return that == that->parent->first_child ? nullptr : that; }