# Invert binary tree in O(1) space without stack/queue/recursion
contributed by < `fennecJ` >

昨天聽了 Jserv 開的直播--[資訊科技產業專案設計](https://youtu.be/Bk5O9xPPf0c?t=9265) ，裡面提到了一個很有趣的問題 : <br>
有沒有辦法不用 recursion 並 Invert binary tree in O(1) space ?( 即無法使用 stack/queue 等額外的資料結構輔助 )

要回答這個問題，我們可以先從 Morris traversal 開始看起。

## Morris traversal
核心精神 : 以 leaf node 作為回到 root 的入口

以往我們在進行 binary tree 的 traversal 時，我們之所以需要用到 recursion 或是 stack/queue 的輔助是因為我們需要有一個方法可以在進入 child node 之後，回到原本的 parent node 。

而 Morris traversal 對這個問題提供了一個解法 :
在 leaf node 的地方新增一個回到 parent 的 link
( 有的人可能會直覺聯想到 [Threaded binary tree](https://www.geeksforgeeks.org/threaded-binary-tree/) ，但兩者仍有決定性的不同， Threaded binary tree 需要在結構內額外開位子存當前 node 的 child 是否為連到 ancestor 的 thread ，而 morris 的做法則不用。 )

我們來看看他的 pseudo code (Morris traversal Inorder) ，
我參考這篇[文章](https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/)做了少許改編 : <br>

* Initialize cur as root
* While cur != NULL
* If the cur->left == NULL
* a) Print cur’s data
* b) cur = cur->right
* Else
* Find rightmost node in cur's left subtree which right child != cur.
* If rightmost node's right child != NULL (it must be cur)
***//Which means there is a link to the cur.***
* Let rightmost node's right child = NULL ***//Break the link***
* Print cur's data
* cur = cur->right.
* Else
* Let rightmost node's right child = cur ***//Build a link***
* cur = cur->left.

觀察上述 pseudo code，第一次進入 tree 的時候，由於沒有 link 存在， cur 會一直往 cur->left 走，直到到 leftmost node(cur->left == NULL) ，才藉由 link 往 parent 走，之後往 parent->right 移動。順序是 left->parent->right ，為 inOrder traversal 的順序。

以下放上熱心網友做的圖[^first]幫助理解:
也可以看熱心網友做的動畫[^second]:

實作程式碼 :

void morris_inOrder(node *head) {
    node *cur = head;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->right && q->right != cur)
                q = q->right;

            if (!q->right) {
                q->right = cur;
                cur = cur->left;
                continue;
            }
            q->right = NULL;
            printf("%d ", cur->data);
            cur = cur->right;
            continue;
        }
        printf("%d ", cur->data);
        cur = cur->right;
    }
}

空間複雜度 : O(1)<br>
時間複雜度 : O(2n) ，因為每個 node 最多只會經過兩次<br>
事實上，只要在將第 15 行的

printf("%d ", cur->data);

移到第 10 行後面 <br>
就可以將其改為 preOrder：

void morris_preOrder(node *head) {
    node *cur = head;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->right && q->right != cur)
                q = q->right;

            if (!q->right) {
                q->right = cur;
                printf("%d ", cur->data);
                cur = cur->left;
                continue;
            }
            q->right = NULL;
            cur = cur->right;
            continue;
        }
        printf("%d ", cur->data);
        cur = cur->right;
    }
}

至於 postOrder ，若要用 morris alg 實作，會稍微複雜一些，這裡暫不討論，有興趣的人可以參考[這篇](https://www.quora.com/What-is-a-good-way-to-implement-stackless-recursion-less-post-order-traversal-for-a-non-threaded-binary-tree-using-Morris-method)

接下來我們回來看看題目。
# Invert binary tree in O(1) space
以 inOrder 或是 preOrder 順序對 tree 進行 invert，若在當前 node 的所有 children 尚未遍歷之前就發生 invert 則會導致原本 left -> root -> right 順序變成 left -> root -> left( 因為 root invert 後原本的 left 和 right child 會互換 )
這樣 cur 究竟要往左或往右走不太好處理。 <br>
我們要確保對一 node invert 之前其所有 children 都遍歷過了。<br>
在 morris traversal 的基礎上進行改編，得到以下程式碼 ( 由 [此篇文章](https://maskray.me/blog/2015-06-16-morris-post-order-traversal) 改編 )

void invert_bin_tree(node *root) {
    node *cur = new_node(0);
    cur->left = root;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->right && q->right != cur)
                q = q->right;
            if (!q->right) {
                q->right = cur;
                cur = cur->left;
                continue;
            }
            node *tmp = cur->left;
            while (tmp) {
                swap(&tmp->left, &tmp->right);
                if (tmp == q)
                    break;
                tmp = tmp->left;
            }
            q->left = NULL;
	    /* Link from q to cur is changed from q->right into q->left,
	       causing by while loop for tmp in line 15. */
        }
        cur = cur->right;
    }
}

不同的地方有幾個點:
* 多了一個 dummy node 指向 root
* 第 12 行原本 break link 應為 `q->right = NULL;` 被改為 `q->left = NULL;`

之所以多了一個 dummy node 並指向 root ，是為了讓 cur 走到 right most node 時，能藉這個 node 走回 root，並對 root 進行 invert 。<br>
而為何從 `q->right = NULL;` 改為 `q->left = NULL;`<br>
是因為在前面的 while(tmp) 中， 會對 tmp 的 left child 以及 right child 進行交換，直到 tmp == q 為止進行最後一次交換。<br>
此時 q 的 left 和 right child 進行交換，導致原本指向 cur 的 right child 變成 left child ，因此要打破這個 link 要用 `q->left = NULL;`
我嘗試做了一個動畫幫助理解 : <br>
可以在[這裡](https://docs.google.com/presentation/d/1sjgbtara7MMqqIXxtd2xf4L0QLjOqJTeBzuH2FPn6hk/edit?usp=sharing)一頁一頁翻

那麼，有沒有辦法可以不額外新增一個 dummy node 呢 ? <br>
近日我在 leetcode 討論區看到 [這個解答](https://leetcode.com/problems/invert-binary-tree/discuss/62781/C%2B%2B-Non-recursive-O(n)-time-O(1)-space-solution-based-on-Morris-Traversal)

正如前面所提，如果用原本的 morris_alg 來做的話，難點在於判斷 cur 何時該往左走，何時該往右走，因此關鍵在於，如何判斷進入一個 node 前該 subtree 已經被翻轉過了 ( 即該 node 的 parent 已經被翻轉過了 )。如果被翻轉過了，那就用翻轉後的方法進行 morris alg ( left 和 right 互換 ) ，否則就照沒翻轉的情形進行 morris alg 。
我們將原本的 morris_inOrder left right 互換，但是仍維持從 cur 的 left subtree 開始處理，因此 q 的 init value 維持 cur->left

void swap_LR_morris_inOrder(node *head) {
    node *cur = head;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->left && q->left != cur)
                q = q->left;

            if (!q->left) {
                q->left = cur;
                cur = cur->right;
                continue;
            }
            q->left = NULL;
            swap(&cur->left, &cur->right);
            cur = cur->left;
            continue;
        }
        swap(&cur->left, &cur->right);
        cur = cur->left;
    }
}

接著在改編後的基礎上加回未翻轉的 morris_alg ，用以下 code 取代原本第 9 行的 `if (!q->left) ` block 的內容

q = cur->left;	// 回到原本 morris_alg 的起點
while (q->right && q->right != cur)
    q = q->right;
if (!q->right) {
    q->right = cur;
    cur = cur->left;
    continue;
}

最後我們就得到了以下 code :

void invert_bin_tree(node *head) {
    node *cur = head;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->left && q->left != cur)
                q = q->left;

            if (!q->left) {
                q = cur->left; // 回到原本 morris_alg 的起點
                while (q->right && q->right != cur)
                    q = q->right;
                if (!q->right) {
                    q->right = cur;
                    cur = cur->left;
                    continue;
                }
            }
            q->left = NULL;
            swap(&cur->left, &cur->right);
            cur = cur->left;
            continue;
        }
        swap(&cur->left, &cur->right);
        cur = cur->left;
    }
}

再來我們對上面的 code 進行簡化，初步觀察可以發現第 `20~22` 行是多餘的，把他刪掉，變成 :

void invert_bin_tree(node *head) {
    node *cur = head;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->left && q->left != cur)
                q = q->left;

            if (!q->left) {
                q = cur->left; // 回到原本 morris_alg 的起點
                while (q->right && q->right != cur)
                    q = q->right;
                if (!q->right) {
                    q->right = cur;
                    cur = cur->left;
                    continue;
                }
            }
            q->left = NULL;
        }
        swap(&cur->left, &cur->right);
        cur = cur->left;
    }
}

接下來我們開始檢視上面的 code 究竟做了什麼 ? <br>
首先一樣從 cur 的 left subtree 開始進行 (`node *q = cur->left;`) <br>
再來是如何判斷進入 cur 之前已經發生了翻轉，由於我們建立 link 時只會從 leaf node 的 ==right== child 連，因此若在 cur 的 children 中存在 node 的 ==left== child 能連回 cur 的話表示這個 node( 作為 cur 的 parent) 已經被翻轉過了。第 9 行的 `if (!q->left)` 就是用來判斷是否有發生翻轉的條件。 <br>
另外，若存在符合以上描述的 node ，此 node 必為 subtree 中的 leftmost node ，因為 cur 第一次進入一個 subtree 時必會一直走到 leftmost node ，之後再藉 link 往回走 ( 第一次進入時狀態為未翻轉，會一直執行第 15 行，往 cur->left 移動 ) 。 <br>
可觀察以下動畫幫助理解 :

也可在 [這裡](https://docs.google.com/presentation/d/1FiUpldrtOE6NKB75fe-ebRfIi7vUwEZ3zi_JpC3vIE4/edit?usp=sharing) 一頁一頁翻 <br>

基本上以上就是以 morris_alg 進行 invert bin tree 而不用到 dummy node 的做法。 <br>
最後， cur 走回 parent 唯一的路徑只有在 swap 後第 22 行的 `cur = cur->left;` ，因此只要進入 `!q->left` 的區塊，表示目前是 cur 第一次進入該 subtree ，不會事先有 link 存在，第 11 行的 `&& q->right != cur` 以及第 13 行的 `if (!q->right)` 是可以直接拔掉的。

void invert_bin_tree3(node *root) {
    node *cur = root;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->left && q->left != cur)
                q = q->left;
            if (!q->left) {
                q = cur->left;
                while (q->right)
                    q = q->right;

                q->right = cur;
                cur = cur->left;
                continue;
            }
            q->left = NULL;
        }
        swap(&cur->right, &cur->left);
        cur = cur->left;
    }
}

以上 code 皆可到 [我的 Github](https://github.com/fennecJ/alg_practice/blob/master/morris_traversal.c) 上下載，最後附上 [LeetCode 226.](https://leetcode.com/problems/invert-binary-tree/) 的解答 :

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

inline void swap(struct TreeNode  **a, struct TreeNode  **b) {
    struct TreeNode  *tmp = *a;
    *a = *b;
    *b = tmp;
}

struct TreeNode* invertTree(struct TreeNode* root){
    struct TreeNode *cur = root;
    while (cur) {
        struct TreeNode *q = cur->left;
        if (q) {
            while (q->left && q->left != cur)
                q = q->left;
            if (!q->left) {
                q = cur->left;
                while (q->right)
                    q = q->right;
                
                q->right = cur;
                cur = cur->left;
                continue;
            }
            q->left = NULL;
        }
        swap(&cur->left, &cur->right);
        cur = cur->left;
    }
    return root;
}

#### 參考資料

* [Inorder Tree Traversal without recursion and without stack!](https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/)
* [Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）](https://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html)
* [Explain Morris inorder tree traversal without using stacks or recursion](https://stackoverflow.com/a/58191797/16028494)
* [What is a good way to implement stackless/recursion less post order traversal for a non threaded binary tree using Morris method?](https://www.quora.com/What-is-a-good-way-to-implement-stackless-recursion-less-post-order-traversal-for-a-non-threaded-binary-tree-using-Morris-method)
* [常數空間Invert Binary Tree與仿Morris法後序遍歷](https://maskray.me/blog/2015-06-16-morris-post-order-traversal)
* [C++ Non-recursive O(n) time O(1) space solution, based on Morris Traversal](https://leetcode.com/problems/invert-binary-tree/discuss/62781/C%2B%2B-Non-recursive-O(n)-time-O(1)-space-solution-based-on-Morris-Traversal)

[^first]: [Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）](https://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html)
[^second]: [Explain Morris inorder tree traversal without using stacks or recursion](https://stackoverflow.com/a/58191797/16028494)