Hey LeetCoders,

I hope you're all doing well and enjoying your coding journey! Today, I want to share an incredible tree traversal technique that I recently stumbled upon: Morris Traversal. If you're looking for a way to perform an inorder traversal without using any extra space (not even a stack or recursion), this is the technique for you!

What is Morris Traversal?
Morris Traversal is an algorithm for inorder traversal of a binary tree using O(1) space. Unlike traditional methods that use a stack or recursion, Morris Traversal leverages the tree's structure to eliminate extra space usage. This makes it a highly efficient technique, especially for large trees where memory usage can be a concern.

How Does It Work?
The key idea is to make use of the threaded binary tree concept, where we temporarily modify the tree's structure during the traversal process. Here's a brief overview of the steps:

1. Initialize: Start with the current node as the root.
2. Left Subtree Check: If the current node has no left child, visit the current node and move to its right child.
3. Threading: If the current node has a left child, find its inorder predecessor (the rightmost node in the current node's left subtree).
   a. If the predecessor's right child is NULL, make the current node the right child of the predecessor and move to the current node's left child.
   b. If the predecessor's right child is the current node, revert the changes (set the predecessor's right child to NULL), visit the current node, and move to its right child.
4. Repeat: Continue the process until the current node becomes NULL.

Example Code:

vector inorderTraversal(TreeNode* root) {
vector inorder;
TreeNode* current = root;
while (current != NULL) {
if (current->left == NULL) {
inorder.push_back(current->val);
current = current->right;
} else {
TreeNode* prev = current->left;
while (prev->right && prev->right != current) {
prev = prev->right;
}
if (prev->right == NULL) {
prev->right = current;
current = current->left;
} else {
prev->right = NULL;
inorder.push_back(current->val);
current = current->right;
}
}
}
return inorder;
}

Why Use Morris Traversal?

• Space Efficiency: Uses O(1) space by avoiding stack/recursion.
• Inorder Sequence: Preserves the natural inorder sequence.
• Optimal for Large Trees: Great for scenarios where memory usage is critical.

Conclusion
Morris Traversal is a game-changer for tree traversal problems, offering a space-efficient solution without compromising on the traversal order. Give it a try on your next binary tree problem and see the magic unfold!

Feel free to share your thoughts, optimizations, or any interesting problems where you think Morris Traversal can be particularly useful. Let's discuss and learn together!

Happy coding! 🚀