Programming Puzzles: Python Edition

Background

The in-order traversal algorithm visits each node exactly once, so the time complexity of the algorithm is O(n) and the space complexity is O(h) where h is the height of the tree.

It is possible to perform an in-order traversal of a binary tree with constant space complexity O(1) using the morris traversal algorithm. The algorithm works as follows:

1. Initialise the current node to the root of the tree.
2. If the current node has no left child, yield its value and move to its right child.
3. If the current node has a left child, find its in-order predecessor (i.e. the rightmost node in its left subtree):
   1. If the predecessor has no right child, set its right child to the current node and move to the left child of the current node.
   2. Else if ...