二分探索木の削除実装 Elixir(Beta)編（paizaランク B 相当）

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

問題

N 個の整数 t₁, t₂, ..., t_N と M 個の整数 a₁, a₂, ..., a_N が与えられます。

次のルールに従って二分探索木を作成した後、値が a_i である M 個のノードを順番に削除し、木のノードを先行順で訪問した結果を出力してください。

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

・ 入力で与えられる t₁, t₂, ..., t_N の順に二分探索木に挿入する
・ 左の子ノードの値は現在のノードの値よりも小さい
・ 右の子ノードの値は現在のノードの値よりも大きい
・ 削除するノードがあった場所には、削除するノードより大きい値を持つノードのうち、最小の値を持つノードが来る

先行順とは、根から順に左部分木、右部分木を訪問する操作方法です。

先行順は再帰を用いた以下のアルゴリズムによって実装できます。

・ 訪問したノードを出力する
・ 左の子がある場合、左の子を訪問する
・ 右の子がある場合、右の子を訪問する
・ 親ノードに戻る

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

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

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

入力される値

N
t₁ t₂ ... t_N
M
a₁ a₂ ... a_M

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

期待する出力

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

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

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

条件

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

・ 3 ≦ N ≦ 100

・ 1 ≦ M ≦ N-2

・ 1 ≦ t_i ≦ 1000

・ 1 ≦ a_i ≦ 1000

・ a_i ∈ t

・ t_i ≠ t_j (i ≠ j)

・ a_i ≠ a_j (i ≠ j)