Skip to main content

Morris Traversal

Learn Morris Traversal (Trees, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Inorder Traversal with O(1) Space - No Stack, No Recursion Every other traversal method needs O(h) extra space (call stack or explicit stack). Morris Traversal achieves O(1) EXTRA space by temporarily rewiring the tree itself: for each node with a left subtree, find its INORDER PREDECESSOR (the rightmost node in the left subtree) and make that predecessor's right pointer temporarily point back to the current node - a "thread" that lets traversal return upward without a stack.

More lessons in Trees