再帰もスタックも使わない！Morris Pre Order Traversalをゼロから理解しよう

「二分木の探索って、再帰かスタックを使うのが当たり前じゃないの？」そう思っている方、多いんじゃないでしょうか。

実は、再帰もスタックも一切使わず、さらに追加メモリO(1)で二分木を走査するアルゴリズムがあるんです。それが今回紹介する Morris Pre Order Traversal（モリス前順走査） です。🌳

アルゴリズムの面接対策としても話題になっているテクニックなので、ぜひ一緒に理解していきましょう！

Contents

そもそもPreorder Traversal（前順走査）とは？
Morris Pre Order Traversalの仕組み 🔍
Pythonで実装してみよう 🐍
まとめ 📝

そもそもPreorder Traversal（前順走査）とは？

binary tree algorithm / Photo by Thomas P via Pexels

二分木の走査には大きく3種類あります。

✅ Preorder（前順）：ルート → 左 → 右
Inorder（中順）：左 → ルート → 右
Postorder（後順）：左 → 右 → ルート

通常の前順走査は再帰やスタックで簡単に書けますが、それだとO(n)の追加メモリが必要になります。Morris法はこれをO(1)に抑えるのがポイントです。

Morris Pre Order Traversalの仕組み 🔍

イメージとしては、「木の中に一時的なリンクを張って、戻り道を作る」という感じです。

具体的には、現在のノードの左部分木の右端（inorder predecessor）を探して、そこに一時リンク（スレッド）を張ります。これによって、スタックなしで親ノードに戻れるようになります。

ざっくりとした流れをまとめるとこんな感じです。

現在ノード（curr）がNoneになるまでループ
左の子がなければ → 値を記録して右へ進む
左の子があれば → 左部分木の右端ノード（predecessor）を探す
predecessorの右がNoneなら → 値を記録し、一時リンクを張って左へ進む
predecessorの右がcurrなら → リンクを外して右へ進む

Pythonで実装してみよう 🐍

ポイントをコメント付きで書いてみます。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def morris_preorder(root):
    result = []
    curr = root

    while curr:
        if curr.left is None:
            # 左の子がなければ値を記録して右へ
            result.append(curr.val)
            curr = curr.right
        else:
            # 左部分木の右端（predecessor）を探す
            predecessor = curr.left
            while predecessor.right and predecessor.right != curr:
                predecessor = predecessor.right

            if predecessor.right is None:
                # 一時リンクを張って左へ進む（ここで値を記録！）
                result.append(curr.val)  # Preorderなので先に記録
                predecessor.right = curr
                curr = curr.left
            else:
                # 一時リンクを外して右へ進む
                predecessor.right = None
                curr = curr.right

    return result

# テスト用の木を作成
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(morris_preorder(root))

ここが重要です。Inorder版との違いは値を記録するタイミングだけです。Preorderでは「左の子がない」か「一時リンクを新たに張る直前」に値を記録します。この1箇所の違いを意識するだけで、Inorderとの使い分けがぐっと楽になりますよ。