Morris Traversal
O(1)-space traversal by temporarily threading each node's inorder predecessor to it.
Tree Traversals: Inorder with threads instead of a stack
50 has a left subtree, so something comes before it. Its inorder predecessor is 40, the rightmost node on its left. That node's right pointer is empty, so the left subtree has not been walked yet.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(1)
Before this
Variants
- Morris Inorder
- Morris Preorder
- Morris Postorder
Taught by the same lesson
Tree Traversals covers these too, in the same run.