For example exist linked list with thousands (maybe million) elements or very deep tree which some branches are very long and have only one child, but exists other short branches with many children. How process this lists and trees changing very deep recursion to iteration? I have

struct Node {
Node* next;
};


but also can exists other types and have more pointers:

struct Node1: public Node {
Node* next1;
Node* next2;
};


Now I want use recursion if have > 1 non empty pointers, but iterate over long series ..next->next->next->... I don't know which pointer will have long or short series.

When processing a node, follow the unique outgoing path until reaching a node with two children, and only then recurse.

In pseudocode:

process-all(node v):
loop
process v
split into cases according to the number of children that v has:
no children: quit the entire procedure
one child: replace v with its unique child
two children: break out of the loop
end loop
process-all(first child of v)
process-all(second child of v)