infinite loop while counting size of tree with circular references

[crazywkb]

I met a problem when implementing the morris traversal algorithm using this package, the simplified code is as follows:

from binarytree import build

# morris traversal algorithm will cause circular references
# but it will be solved while traveling again
def cycle(root):
    condition = True

    while root:
        if condition:
            root.right = root
            condition = False

        else:
            root.right = None


if __name__ == '__main__':
    node = build([1,2,3,4,5])
    cycle(node)

the while statement will call the root.__len__(), which will get size by level traversal. But if there is a circular references like above, level traversal will get into infinite loop without any message about it. Changing the while statement to while root is not None can solve this, but I think it would be better to raise some message if this happened.

Suggestions:

1. len(node) can get correct size of node even though there is circular references.
   you can use set to record the visited node while counting size of node using level traversal. Besides, while node, if node looks more graceful than while node is not None, if node is not None.

2. if the first proposal is rejected, please raise some error message or warning while get into len(node) infinite loop.

[joowani]

Hi @crazywkb,

Your cycle function seems to have a bug (it will never terminate if the input is not falsy), but I get your point. I prefer option 2 as it doesn't try to hide anything from the users. The earlier the users discover that their tree has a problem the better. I will look into adding a circular dependency check in the next release. Thanks for bringing this up!

[joowani]

There is already a way to validate the tree (including circular dependency checks) via binarytree.Node.validate. After some thought, I decided to leave it up to the user to call this validate method explicitly rather than calling it in all methods like len.

The reasoning is as follows:

1. I've seen this library being used to teach students. The teacher, for example, may want to intentionally trigger an infinite loop or a break the binary tree for educational/demonstration purposes. A far-fetched example, but the point is that I'd rather give the users the freedom of choice.
2. Extra computation required for every method.