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
- Binary Tree
- Binary Search Tree - BST
- Full / Complete / Perfect Binary Tree
- Balanced Tree
- Tree Traversal - Preorder
- Tree Traversal - Inorder
- Tree Traversal - Postorder
- Tree Traversal - Level Order
- Recursive Traversal
- Iterative Traversal
- Height / Depth
- Diameter of a Tree
- Lowest Common Ancestor
- Path Sum
- Tree View - Left View
- Tree View - Right View
- Tree View - Top View
- Tree View - Bottom View
- Boundary Traversal
- Vertical Traversal
- Zigzag Traversal
- Serialize / Deserialize a Tree
- BST Operations
- BST Validation
- Kth Smallest / Largest in BST