Approach Summary
Morris traversal: for each node, find the rightmost node of the left subtree, attach right child there, move left subtree to right, set left = null.
How to Recognize This Pattern
- In-place preorder flatten — no extra space
- Morris: stitch left's rightmost to right, then move left
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Linked List Stack Tree DFS Binary Tree