二分探索木の高さを揃える D(Beta)編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

3 個の整数 t₁, t₂, t₃ が与えられます。

次のルールに従って二分探索木を作成した後、木の回転を用いて t₁ の左右の部分木の高さの差を 1 以下にして、木のノードを先行順で訪問した結果を出力してください。

全てのノードについて、以下が成り立つ

・ 入力で与えられる t₁, t₂, ..., t_N の順に二分探索木に挿入する
・ 左の子ノードの値は現在のノードの値よりも小さい
・ 右の子ノードの値は現在のノードの値よりも大きい

木構造は、ノード同士が関係性を持つことで作ることができます。

この問題で各ノードが持つべき情報は以下の通りです。

・ ノードの値
・ 親ノードの情報
・ 左の子ノードの情報
・ 右の子ノードの情報

入力される値

3
t₁ t₂ t₃

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力

作成した木の N 個のノードの値 t_i を先行順で訪問した結果を出力してください。

訪問先にノードがある場合、訪問したノードの値 t_i を1行ずつ出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・ N = 3

・ 1 ≦ t_i ≦ 1000

・ t_i ≠ t_j (i ≠ j)