2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.