parikshan

invert-binary-tree

Difficulty: Easy  ·  Topic: Trees  ·  Practice it on parikshan: /practice/invert-binary-tree/start

The story

A localisation team at a global commerce platform supports both left-to-right languages (English, Hindi, German) and right-to-left languages (Arabic, Hebrew, Urdu). When the layout engine paints a navigation tree, the LTR rendering puts first child on the left, last child on the right. For an Arabic user, the entire tree has to flip horizontally so the same content reads right-to-left. The engine cannot reorder the source data: it has to take whatever tree the content team produced and return a mirror image of it for display. The flip happens at every node, all the way down.

That is invert-binary-tree. Once you see this problem in this framing, you will recognise it whenever a UI mirrors a layout, a graph is flipped for a different reading direction, or a structure is reversed for a comparison.

What's actually being asked

Given a binary tree, return a new tree (or mutate in place) where at every node the left child and right child have been swapped. The whole subtree under each child rides along; the values do not change.

The input is a level-order JSON array with null for missing children. The output is the inverted tree, encoded the same way, with trailing nulls trimmed.

The naive approach

Convert the tree to some intermediate form (a list of paths, a flat array indexed by position) then reconstruct it mirrored. That can be made to work, but every step risks dropping the structural correspondence between input and output, and the intermediate representation costs O(n) extra memory for no algorithmic gain.

The other naive trap is recursing without checking for None: node.left, node.right = invert(node.right), invert(node.left) assumes node is real. If the function is ever called on an empty subtree, it crashes. The empty tree must short-circuit.

The key insight

Inversion is a one-line mutation: at every node, swap left and right. The "at every node" part is a tree walk. The walk can be DFS or BFS, pre-order or post-order; for this problem the order does not matter because each swap is independent of every other swap. That independence is what makes the problem easy. Most tree problems require the children's answers before you can compute the parent's; this one does not.

So the recursion has the shape of the Trees primer's first canonical recursion, but the "return a value" is the inverted subtree itself.

Step-by-step approach

  1. Parse the level-order array into a tree of nodes.
  2. Define invert(node):
    • If node is None, return.
    • Swap node.left and node.right.
    • Recurse into the new node.left and node.right.
  3. Call invert(root).
  4. Encode the mutated tree back to level-order with null placeholders for the missing children of real nodes, then strip trailing nulls and print.

For a 10,000-node skewed input, replace the recursion with an explicit stack. Push the root, pop, swap, push the (now-swapped) children. Same O(n) time, no stack overflow.

Worked example

Input: [4, 2, 7, 1, 3, 6, 9]

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

Output: [4, 7, 2, 9, 6, 3, 1]

Walk the tree post-order, swap at each node:

  • At 1: no children, swap is a no-op.
  • At 3: no children.
  • At 2: swap to give right=1, left=3.
  • At 6, 9: leaves.
  • At 7: swap to give right=6, left=9.
  • At 4: swap to give right=2, left=7.

Level-order read of the result: 4, 7, 2, 9, 6, 3, 1.

Complexity

  • Time: O(n). Each node is visited once; each swap is O(1).
  • Space: O(h) for the recursion stack, or O(width) for a BFS queue.

There is no faster algorithm. You have to touch every node to know that it was swapped, and you have to emit every node to encode the result.

Common pitfalls

  • Encoding the output wrong: the level-order encoding has a contract. Walk BFS, emit each real node's value, and for every real node already emitted append null or the child's value for both its children. Strip trailing nulls at the end. Forgetting to strip produces a non-canonical answer that the grader rejects.
  • Stripping trailing nulls too aggressively: in [1, null, 2], the null between 1 and 2 is structural, not trailing; something real follows it. Only the suffix of consecutive nulls at the end is removed.
  • Mutation vs. fresh tree: it does not matter for the answer, but if you mutate and the test harness reuses the original input, future tests fail. The grader here resets between tests, so either approach is fine.
  • Recursing without a base case: invert(None) must do nothing and return. Otherwise the first leaf's child access crashes.

Where this shows up in the enterprise

  • DOM mirroring for RTL languages: the React, Vue, and Lit renderers all walk the DOM to flip directional CSS (margin-left becomes margin-right, flexbox row direction reverses). The conceptual operation is a tree inversion.
  • Git rebase and rewrite tooling: git rebase --interactive shows commits in reverse chronological order in the editor, then writes them back in forward order. The underlying graph operation is structurally an inversion on a portion of the commit DAG.
  • Database query plan transformations: PostgreSQL's planner sometimes mirrors a join tree (left-deep to right-deep) to expose a better access path. The transformation is an in-place inversion at a subtree of the plan tree.
  • Game engines: Unity's scene graph supports a "mirror" transform that inverts the local transform tree under a node for symmetric models (a single asset becomes both the left and right hand).
  • CDN routing tables: when Cloudflare swaps a primary and a failover region for an Anycast deployment, the routing trie under that prefix is effectively inverted for the duration of the failover.
  • AST refactoring: ESLint and Babel transformers occasionally reverse the order of binary operator arguments (e.g. a == b to b == a for readability rules). Repeating that across every comparison in an AST is a special-purpose inversion.

The pattern shows up wherever a hierarchy has a left-right asymmetry that some consumer needs flipped.

Variants you'll see elsewhere

  • flip-equivalent-binary-trees: decide whether two trees can be made equal by some sequence of inversions at chosen nodes.
  • reverse-odd-levels-of-binary-tree: invert only at odd levels.
  • mirror-of-binary-tree: same problem under a different name.
  • same-tree and symmetric-tree: both downstream of this idea, the second one literally asks "is this tree its own inversion".
  • flatten-binary-tree-to-linked-list: a different mutation but the same "walk every node, do an O(1) reshape" pattern.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

  1. The editor runs your code against public tests for instant feedback, and against per-session dynamic private tests (generated freshly per session). The output encoding is the main source of dropped marks; the dynamic tests exercise it on shapes you would not naturally try, including a left-only chain where every right child is null.
  2. Hints are graduated. The first nudge points at the per-node operation; the third gives you the full skeleton. The integrity score tracks how many you take.
  3. The AI training assistant is a sparring partner, not an answer key. Explain, Review, Find Bugs, Add Comments, Optimise are all available in exam mode at a small integrity cost each. In practice mode they are free.
  4. The dispute flow runs after the verdict. If your output is correct but the encoding contract caught you, one click sends the case to a human reviewer.

Read the concept, attempt the problem in practice mode first, accept the integrity hit only when you genuinely need a hint, then redo it in exam mode with no help. When you can produce the canonical encoded output in under five minutes without touching AI, the pattern is in your fingers.

In the AI-integrated workspace

In your future job, you will not write invert by hand. An agent will. Your job is to:

  1. Recognise that "mirror a hierarchy" is an inversion problem and that the per-node operation is the entire algorithm.
  2. Tell the agent precisely: "walk the tree iteratively, swap each node's children, then re-encode level-order and strip trailing nulls".
  3. Read the agent's code and verify (a) the empty-tree base case, (b) the iterative form to avoid stack overflow, and (c) the trailing-null trim in the encoder.
  4. Stress-test on the edge cases the agent will silently miss: the empty tree, a single node, a chain where every node has only a right child, the case [1, null, 2] where one null is structural.

Candidates who can name "this is an in-place tree mutation, the per-node op is the whole algorithm" are the ones who direct AI agents productively. Candidates who cannot recognise the pattern end up reading 60 lines of generated tree-rebuild code and approving it because the sample passes. parikshan is built to train the first kind.