Morris Traversal 主要解決的是 binary tree traversal 的問題，講到 binary tree traversal，一般人直覺就會想到可以做 preorder, inorder, postorder traversal 求解，但是上述方法一般的實作方式(recursive or iterative + stack) 其 空間複雜度皆為 O(n)，原因是我們必須要紀錄尚未走訪的 node，例如在 inorder traversal 中，我們先照著 左子樹-> root ->右子樹的順序遍歷，如果不用 stack 紀錄 root，當我們走訪完左子樹之後就無法回到 root 繼續走訪。那要怎摸在不使用 stack (額外空間) 的情況下完成 traversal 呢？ Morris Traversal 正是為此而生，它可以在 O(1) space 情況下同樣達到 O(n) 時間複雜度完成 traversal。
