Mirror a Tree

#54 · Trees · Intermediate · 55 XP · about 8 min

Write mirror(root) that turns a binary tree into its mirror image: at every node, the left and right children swap places. Change the tree in place and return its root (None for an empty tree).

Each node is a Node with a value val and two children, left and right. The provided build makes a tree from a list in level order (None marks a missing child), and the provided to_list turns a tree back into such a list, which is how the tests read your result.

Examples

      5                 5
    /   \             /   \
   3     8    -->    8     3
  / \   / \         / \   / \
 1   4 7   9       9   7 4   1

to_list(mirror(build([5, 3, 8, 1, 4, 7, 9])))  # returns [5, 8, 3, 9, 7, 4, 1]
to_list(mirror(build([1, 2])))  # returns [1, None, 2]
to_list(mirror(build([])))  # returns []

In the second example the root's only child is on the left, so after mirroring it is on the right.

Constraints

0 to 1,000 nodes; values are integers.

# Provided: do not change

from collections import deque

class Node:

def __init__(self, val, left=None, right=None):

self.val = val

self.left = left

self.right = right

def build(values):

"""Build a tree from a level-order list; None marks a missing child."""

if not values or values[0] is None:

return None

root = Node(values[0])

queue = deque([root])

i = 1

while queue and i < len(values):

node = queue.popleft()

if values[i] is not None:

node.left = Node(values[i])

queue.append(node.left)

i += 1

if i < len(values) and values[i] is not None:

node.right = Node(values[i])

queue.append(node.right)

i += 1

return root

def to_list(root):

"""The tree as a level-order list, without trailing None values."""

values, queue = [], deque([root])

while queue:

node = queue.popleft()

if node is None:

values.append(None)

else:

values.append(node.val)

queue.append(node.left)

queue.append(node.right)

while values and values[-1] is None:

values.pop()

return values

def mirror(root):

# Your code here

pass

print(to_list(mirror(build([5, 3, 8, 1, 4, 7, 9]))))

Ready?

Accept the challenge to start writing. A small timer counts the time this page is in view.

Output appears here.