Pythonで二分木の中間順トラバーサル（Inorder Traversal）を再帰なしで実装する方法

二分木（バイナリツリー）が与えられたとき、再帰を使わずに中間順トラバーサル（Inorder Traversal）で木を走査する方法を解説します。

例えば、次のような二分木があるとします。

この木に対して中間順トラバーサルを行うと、結果は [2,5,7,10,15,20] のようになります。中間順トラバーサルは「左の子 → 親ノード → 右の子」の順にノードを訪問するため、二分探索木の場合は値が昇順に出力されるという特徴があります。

アルゴリズムの考え方

再帰を使わずにスタックを活用することで、この問題を解決できます。手順は以下のとおりです。

• 結果を格納する配列 res と、ノードを一時的に保持するスタック stack を用意し、curr をルートノードに設定する
• 無限ループを実行する
  • curr が null でない間、以下を繰り返す
    • curr をスタックにプッシュし、curr を左の子ノードに更新する
  • スタックの長さが 0 になったら、res を返して終了する
  • スタックから要素をポップし、そのノードの値を res に挿入する
  • curr を右の子ノードに更新する

このアプローチでは、まず左側のノードをすべてスタックに積み、最も深い左端のノードから順に処理していくことで、再帰と同じ動作を模倣しています。

実装例

以下のコードで実際の動作を確認してみましょう。

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

def insert(temp, data):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            temp.left = TreeNode(data)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            temp.right = TreeNode(data)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

class Solution(object):
    def inorderTraversal(self, root):
        res, stack = [], []
        current = root
        while True:
            while current:
                stack.append(current)
                current = current.left
            if len(stack) == 0:
                return res
            node = stack[-1]
            stack.pop(len(stack)-1)
            if node.data != None:
                res.append(node.data)
            current = node.right
        return res

ob1 = Solution()
root = make_tree([10,5,15,2,7,None,20])
print(ob1.inorderTraversal(root))

入力

[10,5,15,2,7,null,20]

出力

[2,5,7,10,15,20]

コードのポイント

この実装における重要なポイントを整理します。

• 時間計算量： 各ノードを一度だけ訪問するため、O(n) です（n はノード数）。
• 空間計算量： スタックに最大で木の高さ分のノードが格納されるため、最悪ケースで O(n) となります。
• null ノードの扱い： 完全二分木を作成する過程で None のノードが含まれるため、値が null のノードは結果に追加しないようにチェックしています。

再帰版と比較するとコードはやや複雑になりますが、深さが非常に大きい木を扱う場合には、Python の再帰呼び出し上限（デフォルトで約1000回）を回避できるため、この反復的な手法が有効です。