# 動的な二分木のノード
class Node:
    Node *parent
    Node *left
    Node *right
    key

# 動的な二分木
class BinaryTree: 
    Node *root

    insert(data):
        Node *x ← root   # 根から探索を開始
        Node *y ← NULL   # x の親

        # 新しいノードの親を決定
        while x ≠ NULL:
            y ← x # 親を設定
            if data < x.key:
                x ← x.left    # 左の子へ移動
            else:
                x ← x.right   # 右の子へ移動

        # ノードを生成してポインタを設定
        Node *z ← ノードを生成
        z.key ← data
        z.left ← NULL
        z.right ← NULL
        z.parent ← y

        if y = NULL: # treeが空の場合
            root ← z
        else if z.key < y.key:
            y.left ← z # z を y の左の子にする
        else:
            y.right ← z # z を y の右の子にする

    inorder(Node *u):
        if u = NULL: return
        inorder(u.left)
        u.keyを出力
        inorder(u.right)