Pythonで二分木の通りがけ走査（Inorder Traversal）を反復的に実装する方法

はじめに

二分木（バイナリツリー）が与えられたとき、その根（ルート）から通りがけ走査（インオーダートラバーサル）の結果をリストとして取得するプログラムを考えてみましょう。

通りがけ走査とは、木に含まれるすべてのノードを以下の順序で訪問する走査方法のことです。

• 左部分木を再帰的に走査する
• 現在のノードを訪問する
• 右部分木を再帰的に走査する

本記事では、この問題を再帰を使わず、反復処理（イテレーティブ）な手法で解く方法を解説します。

アルゴリズムの考え方

例として、次のような二分木を入力とした場合を考えます。

このとき、出力は [12, 13, 4, 16, 7, 14, 22] となります。

この問題を解くための手順は以下のとおりです。

1. 結果を格納するリスト inorder を空の状態で用意する。
2. 作業用のスタック stack を空の状態で用意する。
3. 無限ループの中で以下の処理を繰り返す。
   • root が None でない場合： root をスタックにプッシュし、root をその左の子ノードに更新する。
   • root が None かつスタックが空でない場合： スタックから要素をポップして root とし、その値を inorder の末尾に追加した後、root を右の子ノードに更新する。
   • それ以外の場合： ループを抜ける。
4. 最後に inorder を返す。

ポイントは、左側のノードをたどりながらスタックに経路を記録しておき、行き止まりに達したらスタックから戻りながらノードの値を記録し、右側へ移動するという流れです。これにより再帰呼び出しと同等の動作を明示的なスタックで実現できます。

実装例

それでは、実際のコードを見てみましょう。

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

class Solution:
    def solve(self, root):
        inorder = []
        stack = []
        while True:
            if root:
                # 左端まで進みながらノードをスタックに積む
                stack.append(root)
                root = root.left
            elif stack:
                # 戻ってノードの値を記録し、右側へ移動
                root = stack.pop()
                inorder.append(root.val)
                root = root.right
            else:
                break
        return inorder

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

入力

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)

出力

[12, 13, 4, 16, 7, 14, 22]

計算量について

このアルゴリズムの時間計算量は O(n)（n はノード数）です。各ノードはスタックへのプッシュとポップをそれぞれ1回ずつしか行わないためです。また、空間計算量も最悪ケース（木が一直線に偏っている場合）で O(n) となり、バランスの取れた木であれば O(log n) 程度に抑えられます。

まとめ

再帰を使わない通りがけ走査は、明示的なスタックを活用することで実現できます。「左へ進む」「戻って記録する」「右へ移動する」という3つの動作を繰り返すシンプルな構造なので、深い木を扱う際に再帰によるスタックオーバーフローを避けたい場合にも有効なテクニックです。ぜひ実際にコードを動かして挙動を確認してみてください。