Родовідне дерево

Катя вирішила зобразити своє сімейне дерево на стіні своєї кімнати. Дерево має таку структуру:

• Коренем дерева є сама Катя.

• У Каті є мати й батько, які є відповідно лівим і правим піддеревами.

• Кожна людина в дереві також має матір і батька, тож кожна вершина повинна, у ідеалі, мати ліве й праве піддерева. Однак Катя не знає всіх своїх пра-пра-дідусів і пра-пра-бабусь, тому деякі вершини можуть не мати одного чи обох піддерев.

Катя повісила портрети своїх родичів у кожній вершині, розмістивши власний портрет у корені. Вийшло красиво!

Молодший брат Каті Антон зрозумів, що це дерево може слугувати й його родинним деревом, якщо просто змінити портрет у корені. Трохи поміркувавши, він вирішив використати спільний портрет себе і Каті в корені, зробивши дерево спільним.

Оскільки дерево тепер було спільним, Антон вирішив зробити свій внесок, обрамляючи всі портрети рамками, які він зробив сам. Нещодавно він навчився робити гарні рамки у дитячому садочку. Скоро в нього було достатньо кольорових рамок. Поки Катя була відсутня, Антон вирішив здійснити задумане. Він почав із того, що знімав усі листки, починаючи з найбільш лівого. (Листок — це вершина без піддерев.) Зняті портрети складалися в стос і відправлялися до його кімнати. Він повторював процес, поки не залишився тільки портрет Каті, який він також забрав до своєї кімнати.

У цей момент Антон із жахом усвідомив, що не може відновити дерево зі стосів портретів, які він зібрав! Катя скоро повернеться з університету, і Антон боявся, що його чекають великі неприємності. Допоможіть Антону відновити дерево! Використовуйте ті літерні позначки, які Катя написала на кожній вершині дерева. Кожна вершина задовольняє такі умови:

• Позначки всіх вершин у лівому піддереві розташовані в алфавітному порядку перед позначкою поточної вершини.

• Позначки всіх вершин у правому піддереві ідуть в алфавітному порядку після позначки поточної вершини.

На малюнку показано приклад дерева та порядок дій Антона.