Morris traversal allows O(1) space inorder traversal of binary trees. Runtime is still O(n) where n is # of nodes in tree. Based on threaded binary tree.
Binary tree traversal usually takes O(h) space on a (recursive) stack, where h is the height of the tree.
Create links to in-order successor and print data using these links, then revert changes to restore the tree.
Essentially we are recursively saying, after processing the left subtree, go to the parent but doing this via a link rather than the recursive stack.
1. Initialize current as root 2. While current is not NULL If current has left child a) Make current as right child of the rightmost node in current's left subtree b) Go to this left child, i.e., current = current->left Else a) Print current’s data b) Go to the right, i.e., current = current->right
class Node: def __init__(self, x): self.val = x self.left = None self.right = None def morris(node): current = node while current: if not current.left: print(current.val) current = current.right continue # find predecessor in left subtree prev = current.left while prev.right and prev.right != current: prev = prev.right # set link if not prev.right: prev.right = current current = current.left continue # undo link to restore tree prev.right = None print current.val current = current.right