Mirror the tree

Easy

2000 ms limit256 MB memoryTrees

Stuck?

Show a hint

Swap a node's two children, then do the same to each of them. An empty node needs nothing done.

The ideas behind this problem

Recursion: trusting the smaller problem Traversals: four orders, and which question each answers Trees: one thing above, several below

Next in this lesson

How many ways up the stairs

Swap every node's two children, all the way down, and return the root.

How the input is written#

Level by level, with null where a child is missing. So 4 2 7 1 3 6 9 is:

        4
      /   \
     2     7
    / \   / \
   1   3 6   9

Worked example#

Mirroring that tree swaps the children of every node, not only the root:

        4                 4
      /   \             /   \
     2     7    ->      7     2
    / \   / \         / \   / \
   1   3 6   9        9   6 3   1

So the answer is 4 7 2 9 6 3 1.

Notice 1 and 9 have traded places even though neither is a child of the root. Swapping only the top two would give 4 7 2 1 3 6 9, which is wrong, and it is the usual first attempt.

The idea#

The answer for a node is: swap its two children, then mirror each of them. That is the whole thing.

mirror(node):
    if node is missing, there is nothing to do
    swap node.left and node.right
    mirror(node.left)
    mirror(node.right)

Swapping before or after recursing both work, as long as you are consistent. What does not work is swapping the children's contents instead of the references.

The cost#

Time O(n), since every node is visited once. Memory O(h) for the call stack, where h is the height.

Constraints#

0 <= number of nodes <= 10000
-100 <= value <= 100

Input

root is a count then that many level order tokens, null for a missing child.

Output

The mirrored tree, level by level, with null for a missing child.

Examples

Input

7
4 2 7 1 3 6 9

Output

4 7 2 9 6 3 1

Every node's children swap, so 1 and 9 end up at opposite ends.

Input

3
2 1 3

Output

2 3 1

Only the root has children, so one swap.

Input

Output

An empty tree mirrors to an empty tree.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.