The Mirror Flip

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Citadel

Problem

Our hierarchy exports render backwards on the new right-to-left dashboard layout, so we need each binary tree flipped before it is drawn. The tree arrives as nested dicts of val, left and right; return its mirror image, with left and right children exchanged at every node all the way down, not just at the top.

Sometimes the fastest fix is to swap everything.

Example 1

Input:

root = {"val":4,"left":{"val":2,"left":{"val":1,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}},"right":{"val":7,"left":{"val":6,"left":null,"right":null},"right":{"val":9,"left":null,"right":null}}}

Output:

{"val":4,"left":{"val":7,"left":{"val":9,"left":null,"right":null},"right":{"val":6,"left":null,"right":null}},"right":{"val":2,"left":{"val":3,"left":null,"right":null},"right":{"val":1,"left":null,"right":null}}}

Example 2

Input:

root = null

Output:

null

Worked solution and explanation

What this really is

This is a depth-first rebuild dressed up as a layout fix. A node's mirror depends on the mirrors of both its children, so the answer is assembled bottom-up from the leaves. Anyone can swap the root's two children. What separates candidates is carrying that swap all the way down, stopping cleanly at None, and reading children as root["left"] rather than root.left, because these are dicts, not node objects. Miss the recursion and only the top level flips. Overwrite left before reading it and one subtree gets silently duplicated while the other vanishes.

Break down the requirements

Step 1: Stop at a None node

If the node is None, return None. That single guard covers the empty tree and stops the descent at every missing child, so no other null checks are needed.

Step 2: Read children by key

Each node is a dict with keys val, left and right. Read the children with root["left"] and root["right"]; there is no attribute to reach for.

Step 3: Mirror both subtrees, then cross them

Mirror the right subtree and place it on the left, then mirror the left subtree and place it on the right. Because both results are computed from the original children, nothing is overwritten before it has been read.

Step 4: Return a new node

Build a fresh dict that carries the same val and return it, so the parent can attach the mirrored subtree. A None child comes back as None and lands in its new position unchanged.

The solution

Recursive swap at every node
def invert_tree(root):
    if root is None:
        return None
    return {
        "val": root["val"],
        "left": invert_tree(root["right"]),
        "right": invert_tree(root["left"]),
    }

Common follow-up questions