二分探索木II

A: Binary Search Tree I に、find 命令を追加し、二分探索木 $T$ に対し、以下の命令を実行するプログラムを作成してください。

• insert $k$: $T$にキー $k$ を挿入する。
• find $k$: $T$にキー $k$ が存在するか否かを報告する。
• print: キーを木の中間順巡回(inorder tree walk)と先行順巡回(preorder tree walk)アルゴリズムで出力する。

入力

入力の最初の行に、命令の数 $m$ が与えられます。続く$m$ 行目に、insert $k$、find $k$ またはprintの形式で命令が１行に与えられます。

出力

find $k$ 命令ごとに、$T$ に $k$ が含まれる場合 yes と、含まれない場合 no と１行に出力してください。

さらに print 命令ごとに、中間順巡回アルゴリズム、先行順巡回アルゴリズムによって得られるキーの順列をそれぞれ１行に出力してください。各キーの前に１つの空白を出力してください。

制約

• 命令の数は $500,000$ を超えない。
• print 命令の数は $10$ を超えない。
• $-2,000,000,000 \leq キー \leq 2,000,000,000$
• 上記の疑似コードのアルゴリズムに従う場合、木の高さは $100$ を超えない。
• ２分探索木中のキーに重複は発生しない。

入力例 1

10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
insert 17
insert 25
find 16
print

出力例 1

yes
no
 1 12 17 20 25 30 88
 30 12 1 20 17 25 88

参考文献

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

---