AlgoScope

Morris Traversal

O(1)-space traversal by temporarily threading each node's inorder predecessor to it.

Tree algorithms, algorithm, advanced
Predecessor of 50 is 40.20304050607080currentpred
Predecessor of 50 is 40.20304050607080currentpred

Tree Traversals: Inorder with threads instead of a stack

Decision, step 2 of 18

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.

How tree traversals works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Before this

Variants

  • Morris InorderThread predecessor to node.
  • Morris PreorderOutput on thread creation.
  • Morris PostorderVia a dummy root and reversed right chains.

Taught by the same lesson

Tree Traversals covers these too, in the same run.