DSA-078 · Swap ownership of the two child edges at every identity

Invert Binary Tree

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 23498 deterministic checks. Learner drafts are not executed.

Understand the problem

Invert a binary tree in place and return the original root reference. Each node’s old left subtree becomes its right subtree and vice versa.

Input roots are null or finite proper binary trees with at most 100,000 nodes per tree: no cycles and no shared child within one tree. Values span the full int domain. Structure/size are preconditions, not an extra validation traversal.
Mutation is permitted only on left/right links. Return the same root object, or null for empty input; allocate no replacement tree nodes. Original values and the set of reachable identities must be preserved.
Inverting twice restores every original edge. The caller must permit destructive mirroring; external references still identify the same objects, now in mirrored positions.

Examples

Input: [4,2,7,1,3,6,9]
Output: same root; [4,7,2,9,6,3,1]
Swap at every node, not only at the root.
Input: [1,1,null,1]
Output: same root; [1,null,1,null,1]
Duplicate values do not identify nodes; each original edge has an exact mirror destination.

Before you start

Proper binary trees and reference identity
Explicit depth-first traversal and mutation ownership

Recognize the structure

This is a structural involution. Swapping a node’s two links and then processing both children covers every local edge. No numeric ordering or BST assumption is involved.

Try before revealing

Hint 1

What two references belong to one local swap?

Hint 2

Save one child before overwriting either link.

Hint 3

Use an explicit stack, swap once per node, and push both nonnull new children.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Recursive local mirror

For null return null. Recursively invert the old left and right subtrees, then assign the results to opposite sides. On [2,1,3], the child leaves stay leaves and root links exchange 1 and 3. Work is already O(n); the explicit-stack implementation replaces recursion so the declared 100,000-node chain is supported.

Improve the baseline

Save before overwriting

Pop a nonnull node and save oldLeft. Set left to the old right, then right to oldLeft; overwriting without the saved reference loses a subtree.

Schedule the new children

After the swap, push new right then new left. The new left is processed next. Both are original children and each is scheduled once.

Preserve the caller’s root

The root variable never changes. Return it directly; pending traversal entries are auxiliary references, not copied nodes.

Why it is correct

Local edge invariant

For every completed node, its left and right links are exactly the original right and left. All values remain unchanged.

Coverage and termination

Only original children are scheduled. In a proper tree each nonroot has one parent, so every node is processed once and no node is lost or duplicated.

Global mirror and involution

Every edge position is reversed at its parent, so all root-relative L/R paths are complemented. Applying the same local swap a second time restores each edge exactly.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    public static final class Node {
        public final int value;
        public Node left, right;
        public Node(int value) { this.value = value; }
    }
    public static Node invert(Node root) {
        if (root == null) return null;
        ArrayDeque<Node> pending = new ArrayDeque<>();
        pending.push(root);
        while (!pending.isEmpty()) {
            Node node = pending.pop();
            Node oldLeft = node.left;
            node.left = node.right;
            node.right = oldLeft;
            if (node.right != null) pending.push(node.right);
            if (node.left != null) pending.push(node.left);
        }
        return root;
    }
    public static Node baseline(Node root) {
        if (root == null) return null;
        Node left = baseline(root.left), right = baseline(root.right);
        root.left = right; root.right = left;
        return root;
    }
}

Read the meaningful blocks

Keep oldLeft alive

The temporary reference protects the subtree before left is overwritten.

Push only nonnull nodes

ArrayDeque rejects null elements; empty input returns before creating traversal work.

Check graph identity, not only values

A value-only level order could hide replacement nodes or aliasing. Tests compare each original object’s two expected links.

Complexity

Both implementations take O(n) time. The main method retains O(h) pending references in the worst case; a single-child chain itself retains only one pending node. Output is the reused root, not an O(n) clone.

Recursive baseline space is O(h) call frames and can overflow on deep chains. A BFS mirror would use O(w) queue space. These are robustness/space tradeoffs, not a faster asymptotic traversal.

Exact-state walkthroughs

Reveal normal and boundary traces

Mirror each original identity

Input: [4,2,7,1,3,6,9] · Returned original root identity: "T0"

Step 1 of 9: Start with the original root identity.

Pending entries are original identities, with top at the right. No replacement tree nodes are allocated.

Inversion — original identities and swapped links

Phase: initial. Current identity: null.

Original objects — current mutated edges

T0: 4left → T1right → T2
T1: 2left → T3right → T4
T2: 7left → T5right → T6
T3: 1left → nullright → null
T4: 3left → nullright → null
T5: 6left → nullright → null
T6: 9left → nullright → null

Pending original nodes — stack top at right

Nodes whose two original edges have been exchanged

Empty.

Card order is identity order, not a picture of the mirrored layout. Returning the same root does not mean the links stayed unchanged.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":4,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":7,"left":"T5","right":"T6"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null},{"id":"T5","value":6,"left":null,"right":null},{"id":"T6","value":9,"left":null,"right":null}]`
root	`"T0"`
pending	`["T0"]`
completed	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     public static Node invert(Node root) {
 9         if (root == null) return null;
10         ArrayDeque<Node> pending = new ArrayDeque<>();
11         pending.push(root);
12         while (!pending.isEmpty()) {
13             Node node = pending.pop();
14             Node oldLeft = node.left;
15             node.left = node.right;
16             node.right = oldLeft;
17             if (node.right != null) pending.push(node.right);
18             if (node.left != null) pending.push(node.left);
19         }
20         return root;
21     }
22     public static Node baseline(Node root) {
23         if (root == null) return null;
24         Node left = baseline(root.left), right = baseline(root.right);
25         root.left = right; root.right = left;
26         return root;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start with the original root identity.
Pending entries are original identities, with top at the right. No replacement tree nodes are allocated.
treeNodes
[{"id":"T0","value":4,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":7,"left":"T5","right":"T6"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null},{"id":"T5","value":6,"left":null,"right":null},{"id":"T6","value":9,"left":null,"right":null}]
root
"T0"
pending
["T0"]
completed
[]
phase
"initial"
current
null
Swap one node’s edges, then schedule its new children.
Completed nodes have exactly swapped original edges. Unprocessed node links and all values still match the original graph.
treeNodes
[{"id":"T0","value":4,"left":"T2","right":"T1"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":7,"left":"T5","right":"T6"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null},{"id":"T5","value":6,"left":null,"right":null},{"id":"T6","value":9,"left":null,"right":null}]
root
"T0"
pending
["T1","T2"]
completed
["T0"]
phase
"swap"
current
"T0"
oldLeft
"T1"
oldRight
"T2"
Swap one node’s edges, then schedule its new children.
Completed nodes have exactly swapped original edges. Unprocessed node links and all values still match the original graph.
treeNodes
[{"id":"T0","value":4,"left":"T2","right":"T1"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":7,"left":"T6","right":"T5"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null},{"id":"T5","value":6,"left":null,"right":null},{"id":"T6","value":9,"left":null,"right":null}]
root
"T0"
pending
["T1","T5","T6"]
completed
["T0","T2"]
phase
"swap"
current
"T2"
oldLeft
"T5"
oldRight
"T6"
Swap one node’s edges, then schedule its new children.
Completed nodes have exactly swapped original edges. Unprocessed node links and all values still match the original graph.
treeNodes
[{"id":"T0","value":4,"left":"T2","right":"T1"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":7,"left":"T6","right":"T5"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null},{"id":"T5","value":6,"left":null,"right":null},{"id":"T6","value":9,"left":null,"right":null}]
root
"T0"
pending
["T1","T5"]
completed
["T0","T2","T6"]
phase
"swap"
current
"T6"
oldLeft
null
oldRight
null
Swap one node’s edges, then schedule its new children.
Completed nodes have exactly swapped original edges. Unprocessed node links and all values still match the original graph.
treeNodes
[{"id":"T0","value":4,"left":"T2","right":"T1"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":7,"left":"T6","right":"T5"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null},{"id":"T5","value":6,"left":null,"right":null},{"id":"T6","value":9,"left":null,"right":null}]
root
"T0"
pending
["T1"]
completed
["T0","T2","T6","T5"]
phase
"swap"
current
"T5"
oldLeft
null
oldRight
null
Swap one node’s edges, then schedule its new children.
Completed nodes have exactly swapped original edges. Unprocessed node links and all values still match the original graph.
treeNodes
[{"id":"T0","value":4,"left":"T2","right":"T1"},{"id":"T1","value":2,"left":"T4","right":"T3"},{"id":"T2","value":7,"left":"T6","right":"T5"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null},{"id":"T5","value":6,"left":null,"right":null},{"id":"T6","value":9,"left":null,"right":null}]
root
"T0"
pending
["T3","T4"]
completed
["T0","T2","T6","T5","T1"]
phase
"swap"
current
"T1"
oldLeft
"T3"
oldRight
"T4"
Swap one node’s edges, then schedule its new children.
Completed nodes have exactly swapped original edges. Unprocessed node links and all values still match the original graph.
treeNodes
[{"id":"T0","value":4,"left":"T2","right":"T1"},{"id":"T1","value":2,"left":"T4","right":"T3"},{"id":"T2","value":7,"left":"T6","right":"T5"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null},{"id":"T5","value":6,"left":null,"right":null},{"id":"T6","value":9,"left":null,"right":null}]
root
"T0"
pending
["T3"]
completed
["T0","T2","T6","T5","T1","T4"]
phase
"swap"
current
"T4"
oldLeft
null
oldRight
null
Swap one node’s edges, then schedule its new children.
Completed nodes have exactly swapped original edges. Unprocessed node links and all values still match the original graph.
treeNodes
[{"id":"T0","value":4,"left":"T2","right":"T1"},{"id":"T1","value":2,"left":"T4","right":"T3"},{"id":"T2","value":7,"left":"T6","right":"T5"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null},{"id":"T5","value":6,"left":null,"right":null},{"id":"T6","value":9,"left":null,"right":null}]
root
"T0"
pending
[]
completed
["T0","T2","T6","T5","T1","T4","T3"]
phase
"swap"
current
"T3"
oldLeft
null
oldRight
null
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
"T0"

Duplicate values still have distinct edges

Input: [1,1,null,1] · Returned original root identity: "T0"

Step 1 of 5: Start with the original root identity.

Pending entries are original identities, with top at the right. No replacement tree nodes are allocated.

Inversion — original identities and swapped links

Phase: initial. Current identity: null.

Original objects — current mutated edges

T0: 1left → T1right → null
T1: 1left → T2right → null
T2: 1left → nullright → null

Pending original nodes — stack top at right

Nodes whose two original edges have been exchanged

Empty.

Card order is identity order, not a picture of the mirrored layout. Returning the same root does not mean the links stayed unchanged.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":1,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":null},{"id":"T2","value":1,"left":null,"right":null}]`
root	`"T0"`
pending	`["T0"]`
completed	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     public static Node invert(Node root) {
 9         if (root == null) return null;
10         ArrayDeque<Node> pending = new ArrayDeque<>();
11         pending.push(root);
12         while (!pending.isEmpty()) {
13             Node node = pending.pop();
14             Node oldLeft = node.left;
15             node.left = node.right;
16             node.right = oldLeft;
17             if (node.right != null) pending.push(node.right);
18             if (node.left != null) pending.push(node.left);
19         }
20         return root;
21     }
22     public static Node baseline(Node root) {
23         if (root == null) return null;
24         Node left = baseline(root.left), right = baseline(root.right);
25         root.left = right; root.right = left;
26         return root;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start with the original root identity.
Pending entries are original identities, with top at the right. No replacement tree nodes are allocated.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":null},{"id":"T2","value":1,"left":null,"right":null}]
root
"T0"
pending
["T0"]
completed
[]
phase
"initial"
current
null
Swap one node’s edges, then schedule its new children.
Completed nodes have exactly swapped original edges. Unprocessed node links and all values still match the original graph.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":1,"left":"T2","right":null},{"id":"T2","value":1,"left":null,"right":null}]
root
"T0"
pending
["T1"]
completed
["T0"]
phase
"swap"
current
"T0"
oldLeft
"T1"
oldRight
null
Swap one node’s edges, then schedule its new children.
Completed nodes have exactly swapped original edges. Unprocessed node links and all values still match the original graph.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":1,"left":null,"right":"T2"},{"id":"T2","value":1,"left":null,"right":null}]
root
"T0"
pending
["T2"]
completed
["T0","T1"]
phase
"swap"
current
"T1"
oldLeft
"T2"
oldRight
null
Swap one node’s edges, then schedule its new children.
Completed nodes have exactly swapped original edges. Unprocessed node links and all values still match the original graph.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":1,"left":null,"right":"T2"},{"id":"T2","value":1,"left":null,"right":null}]
root
"T0"
pending
[]
completed
["T0","T1","T2"]
phase
"swap"
current
"T2"
oldLeft
null
oldRight
null
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
"T0"

Empty root

Input: [] · Returned original root identity: null

Step 1 of 2: Start with the original root identity.

Pending entries are original identities, with top at the right. No replacement tree nodes are allocated.

Inversion — original identities and swapped links

Phase: initial. Current identity: null.

Original objects — current mutated edges

Empty tree.

Pending original nodes — stack top at right

Empty.

Nodes whose two original edges have been exchanged

Empty.

Card order is identity order, not a picture of the mirrored layout. Returning the same root does not mean the links stayed unchanged.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[]`
root	`null`
pending	`[]`
completed	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     public static Node invert(Node root) {
 9         if (root == null) return null;
10         ArrayDeque<Node> pending = new ArrayDeque<>();
11         pending.push(root);
12         while (!pending.isEmpty()) {
13             Node node = pending.pop();
14             Node oldLeft = node.left;
15             node.left = node.right;
16             node.right = oldLeft;
17             if (node.right != null) pending.push(node.right);
18             if (node.left != null) pending.push(node.left);
19         }
20         return root;
21     }
22     public static Node baseline(Node root) {
23         if (root == null) return null;
24         Node left = baseline(root.left), right = baseline(root.right);
25         root.left = right; root.right = left;
26         return root;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start with the original root identity.
Pending entries are original identities, with top at the right. No replacement tree nodes are allocated.
treeNodes
[]
root
null
pending
[]
completed
[]
phase
"initial"
current
null
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
null

Test the contract

Input: null
Output: null
No node is pushed.
Input: Single leaf
Output: same leaf identity
Both links remain null.
Input: Duplicate-valued chain
Output: same identities, opposite edge directions
Values cannot substitute for identity checks.
Input: 100,000-node chain; invert twice
Output: all original edges restored
No recursive-stack dependence.

Common mistakes and counterexamples

Overwrite left before saving it

Counterexample: Assigning right=left after left=right gives both links the old right child.

Save oldLeft before either assignment.

Mirror only the root

Counterexample: The grandchildren of [4,2,7,1,3,6,9] remain in the wrong order.

Process every original node.

Return a newly allocated equal-valued tree

Counterexample: The requested output must preserve object ownership and external references.

Return the original root and verify exact swapped edges.

Follow-ups

Return a mirror copy instead.

Allocate one fresh node per source identity and connect copied children to opposite sides. State O(n) output allocation separately from traversal state and prove no source/copy alias.

Invert only nodes at even depth.

Carry depth explicitly; changing the local swap rule does not remove the need to traverse unswapped nodes. Specify whether root depth is zero.

Can this preserve a BST ordering invariant?

Ordinary inversion changes an increasing BST into a decreasing-order tree. If the caller needs an increasing BST, mirroring alone is not the requested operation.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 174/20,000 characters

Self-review

Can I identify which reference must be saved before assignment?Can I prove node coverage and exact edge restoration after two calls?Can I distinguish reused output from auxiliary stack storage?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.