Binary Tree Threading & Morris In-order Traversal

I was doing a Leetcode question: Recover Binary Search Tree. In the follow-up, it asks if you can solve it with O(1) space complexity which turns out to use the Morris Inorder Traversal.

It took me a while to understand why the algorithm works and I’d like to share my thinking process.

Threaded Binary Tree

We can traverse a binary tree iteratively or recursively with the help of a stack and it is very easy to find the left and right children of a node. However, it is hard or even…