Invert a Binary Tree in Python
2 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.
The mirror of a tree is its root with the mirrored right subtree on the left and the mirrored left subtree on the right. That definition is the whole function: invert both subtrees, then hang them back on opposite sides. An empty subtree is already its own mirror, which ends the recursion. Python evaluates both calls on the right of the tuple assignment before it assigns either side, so nothing gets overwritten too early.
def invert_tree(root: TreeNode | None) -> TreeNode | None:
if root is None:
return None
root.left, root.right = invert_tree(root.right), invert_tree(root.left)
return root
Each swap touches only one node, so the order you visit nodes in does not matter. Put the root in a collections.deque, then repeatedly pop a node, swap its two children and push whichever of them exist. That walks the tree breadth-first, one level at a time, with a plain loop instead of function calls, so depth can never hit the recursion limit.
from collections import deque
def invert_tree(root: TreeNode | None) -> TreeNode | None:
queue = deque([root] if root else [])
while queue:
node = queue.popleft()
node.left, node.right = node.right, node.left
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
Invert a Binary Tree in JavaScript
2 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.
Think of the answer for one node: its mirrored right subtree goes on the left and its mirrored left subtree goes on the right. A null node has nothing to flip, which stops the recursion. In JavaScript the swap fits on one line with array destructuring. The array literal on the right is built first, so both recursive calls finish before either property is written, and no temporary variable is needed.
function invertTree(root) {
if (root === null) return null;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root;
}
A swap only ever touches one node, so any visiting order gives the same mirror. This version keeps the current row of the tree in an array called level. A for…of loop swaps every node in it and collects the children into a fresh next array, which becomes the next row. That is a breadth-first walk without a queue class and without shift(), and the call stack never grows.
function invertTree(root) {
let level = root === null ? [] : [root];
while (level.length > 0) {
const next = [];
for (const node of level) {
[node.left, node.right] = [node.right, node.left];
if (node.left !== null) next.push(node.left);
if (node.right !== null) next.push(node.right);
}
level = next;
}
return root;
}
Invert a Binary Tree in TypeScript
2 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.
The mirror of a tree is its root with the mirrored right subtree hung on the left and the mirrored left subtree on the right. null is its own mirror and ends the recursion. The return type TreeNode | null makes that base case part of the signature, and a destructuring assignment evaluates both recursive calls before writing either child, so no temporary is needed.
function invertTree(root: TreeNode | null): TreeNode | null {
if (root === null) return null;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root;
}
Each swap touches one node only, so any visiting order produces the same mirror. Keep a typed TreeNode[] as a queue and walk it with a read index instead of shift(): swap the current node's children, push the ones that exist, move on. The array grows to at most the node count and the call stack never grows at all.
function invertTree(root: TreeNode | null): TreeNode | null {
if (root === null) return null;
const queue: TreeNode[] = [root];
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
[node.left, node.right] = [node.right, node.left];
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
return root;
}
Invert a Binary Tree in Java
2 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.
Stop at null; otherwise store the inverted right subtree in root.left and the inverted left subtree in root.right. Java assigns one field per statement, so the method first copies root.left into a local. Skip that and the second call receives root.left after it was already overwritten: it would invert the old right subtree a second time, putting it back the way it was, and hang it on both sides.
import java.util.*;
public class Main {
static TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = root.left;
root.left = invertTree(root.right);
root.right = invertTree(left);
return root;
}
}
Since a node's swap is independent of every other node's, the loop may visit them in any order, and a queue gives level order for free. Each pass takes the head with poll(), swaps its fields with the same temp-variable trick, then offers the children to the deque. The two != null guards are mandatory: ArrayDeque refuses null elements and would throw NullPointerException on the first leaf.
import java.util.*;
public class Main {
static TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode left = node.left;
node.left = node.right;
node.right = left;
// ArrayDeque rejects null, so only real children go in
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return root;
}
}
Invert a Binary Tree in Go
2 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.
A nil pointer needs no work, so that is the base case. For any other node the body is one statement: root.Left, root.Right = invertTree(root.Right), invertTree(root.Left). The Go spec runs every expression on the right-hand side first, both recursive calls included, and only then stores into the two fields. So the call on root.Left still sees the original left subtree, and no temporary variable is needed.
package main
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
Flipping one node never depends on whether its parent or children were flipped yet, so any visiting order works. A slice makes the simplest queue in Go: seed it with []*TreeNode{root}, then loop while len(queue) > 0, reading queue[0] and reslicing with queue = queue[1:]. The same tuple assignment swaps the two pointers, and only non-nil children get appended, so the loop never has to test for a nil node it popped.
package main
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
queue := []*TreeNode{root}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
node.Left, node.Right = node.Right, node.Left
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
return root
}
Invert a Binary Tree in C#
2 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.
The mirror of a tree is its root with the inverted right subtree hung on the left and the inverted left subtree hung on the right, and null is its own mirror. The method is that definition: two recursive calls and one tuple assignment. C# evaluates the whole right-hand tuple before it deconstructs it into the two fields, so neither child is overwritten before the other call has read it; no temp variable needed.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static TreeNode InvertTree(TreeNode root)
{
if (root == null) return null;
(root.left, root.right) = (InvertTree(root.right), InvertTree(root.left));
return root;
}
}
Every node needs the same one swap and no swap depends on another, so any visiting order works. A Queue<TreeNode> seeded with the root walks the tree level by level: Dequeue a node, swap its children with the same tuple trick, and Enqueue whichever children exist. The queue would accept null, but enqueuing one only means dereferencing it a step later, so the two guards stay.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static TreeNode InvertTree(TreeNode root)
{
if (root == null) return null;
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0)
{
TreeNode node = queue.Dequeue();
(node.left, node.right) = (node.right, node.left);
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
return root;
}
}
Invert a Binary Tree in C++
2 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.
Return at nullptr; otherwise invert both subtrees and hang them back on opposite sides. Recursing first and then calling std::swap(root->left, root->right) keeps it to one line per step with no temporary to forget, and the nodes are changed in place, so the same root pointer comes back.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;
invertTree(root->left);
invertTree(root->right);
swap(root->left, root->right);
return root;
}
};
Every node needs one swap and the order does not matter, so walk the tree level by level with a std::queue<TreeNode*>. Take the front(), pop() it, swap its children and push the ones that are not nullptr. The queue lives on the heap, so a tree that leans one way cannot exhaust the call stack.
#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;
queue<TreeNode*> pending;
pending.push(root);
while (!pending.empty()) {
TreeNode* node = pending.front();
pending.pop();
swap(node->left, node->right);
if (node->left) pending.push(node->left);
if (node->right) pending.push(node->right);
}
return root;
}
};
Invert a Binary Tree in C
2 reference approaches in C, from brute force to the one to reach for. Compare them with yours.
Stop at NULL; otherwise copy root->left into a temporary, store the inverted right subtree in left and the inverted saved one in right. Only pointers move, so nothing is allocated and the same root comes back.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
struct TreeNode* invertTree(struct TreeNode* root) {
if (root == NULL) return NULL;
struct TreeNode* left = root->left;
root->left = invertTree(root->right);
root->right = invertTree(left);
return root;
}
C has no queue type, so make one: a malloc'ed array of struct TreeNode* with a head index to read from and a tail index to write to. Every node enters it once, so 3,000 slots (the node bound) are enough and no slot is ever reused. Take a node, swap its two pointers, append its non-NULL children, and free the array at the end.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODES 3000
struct TreeNode* invertTree(struct TreeNode* root) {
if (root == NULL) return NULL;
struct TreeNode** queue = malloc(MAX_NODES * sizeof *queue);
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
struct TreeNode* node = queue[head++];
struct TreeNode* left = node->left;
node->left = node->right;
node->right = left;
if (node->left) queue[tail++] = node->left;
if (node->right) queue[tail++] = node->right;
}
free(queue);
return root;
}
Invert a Binary Tree in Kotlin
2 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.
Return null for an empty subtree. Otherwise keep the old root.left in a local val, store the inverted right subtree on the left, then the inverted old left subtree on the right. root is a parameter, so after the null check Kotlin smart-casts it to TreeNode and no !! is needed.
class Solution {
fun invertTree(root: TreeNode?): TreeNode? {
if (root == null) return null
val left = root.left
root.left = invertTree(root.right)
root.right = invertTree(left)
return root
}
}
A kotlin.collections.ArrayDeque<TreeNode> holds the nodes still to swap. Each pass takes the head, swaps its children with the a = b.also { b = a } idiom, and queues the children that exist with ?.let. Every node is swapped exactly once and there is no call stack to grow.
class Solution {
fun invertTree(root: TreeNode?): TreeNode? {
if (root == null) return null
val queue = ArrayDeque<TreeNode>()
queue.addLast(root)
while (queue.isNotEmpty()) {
val node = queue.removeFirst()
node.left = node.right.also { node.right = node.left }
node.left?.let { queue.addLast(it) }
node.right?.let { queue.addLast(it) }
}
return root
}
}
Invert a Binary Tree in Rust
2 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.
If there is a node, borrow_mut() it and take() both children, which moves them out and leaves None behind. Hand each one to the recursive call and store the results on the opposite sides. No Rc is cloned, and the mutable borrow ends with the if let block, before root is returned.
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
if let Some(node) = &root {
let mut node = node.borrow_mut();
let left = node.left.take();
let right = node.right.take();
node.left = Self::invert_tree(right);
node.right = Self::invert_tree(left);
}
root
}
}
A VecDeque of Rc handles walks the tree level by level. For each node, reborrow the RefMut as a plain &mut TreeNode so the borrow checker sees two separate fields, swap them with std::mem::swap, then queue a clone of each child that exists. Rc::clone only bumps a counter; the nodes stay in the tree.
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
let mut queue = VecDeque::new();
if let Some(node) = &root {
queue.push_back(Rc::clone(node));
}
while let Some(node) = queue.pop_front() {
let mut guard = node.borrow_mut();
let node = &mut *guard;
std::mem::swap(&mut node.left, &mut node.right);
if let Some(left) = &node.left {
queue.push_back(Rc::clone(left));
}
if let Some(right) = &node.right {
queue.push_back(Rc::clone(right));
}
}
root
}
}
Invert a Binary Tree in Swift
2 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.
guard let returns nil for an empty subtree and unwraps the node otherwise. One tuple assignment then does the swap: Swift evaluates the whole right-hand tuple, both recursive calls, before it writes either property, so no temporary is needed.
class Solution {
func invertTree(_ root: TreeNode?) -> TreeNode? {
guard let root = root else { return nil }
(root.left, root.right) = (invertTree(root.right), invertTree(root.left))
return root
}
}
The standard library has no deque, so the queue is a plain [TreeNode] read through a moving head index: appending is amortized O(1) and nothing is ever removed from the front. Each node's children are swapped with a tuple assignment, and the ones that exist are appended with if let.
class Solution {
func invertTree(_ root: TreeNode?) -> TreeNode? {
guard let root = root else { return nil }
var queue = [root]
var head = 0
while head < queue.count {
let node = queue[head]
head += 1
(node.left, node.right) = (node.right, node.left)
if let left = node.left { queue.append(left) }
if let right = node.right { queue.append(right) }
}
return root
}
}
Invert a Binary Tree in PHP
2 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.
Return null for an empty subtree. Otherwise build the pair of inverted subtrees on the right of an array destructuring assignment and unpack it into $root->left and $root->right. The right-hand array is complete before either property is written, so the swap needs no temporary.
<?php
class Solution {
/**
* @param TreeNode|null $root
* @return TreeNode|null
*/
function invertTree(?TreeNode $root): ?TreeNode {
if ($root === null) {
return null;
}
[$root->left, $root->right] = [$this->invertTree($root->right), $this->invertTree($root->left)];
return $root;
}
}
An SplQueue holds the nodes still to swap, with O(1) enqueue and dequeue. Each pass swaps the head's children with the same destructuring and enqueues the ones that are not null. Objects are handles in PHP, so the nodes in the queue are the tree's own nodes, not copies.
<?php
class Solution {
/**
* @param TreeNode|null $root
* @return TreeNode|null
*/
function invertTree(?TreeNode $root): ?TreeNode {
if ($root === null) {
return null;
}
$queue = new SplQueue();
$queue->enqueue($root);
while (!$queue->isEmpty()) {
$node = $queue->dequeue();
[$node->left, $node->right] = [$node->right, $node->left];
if ($node->left !== null) {
$queue->enqueue($node->left);
}
if ($node->right !== null) {
$queue->enqueue($node->right);
}
}
return $root;
}
}
Invert a Binary Tree in Ruby
2 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.
Return nil for an empty subtree. Otherwise one parallel assignment does the work: Ruby evaluates both recursive calls on the right before it calls the left= and right= setters, so the old children are still in place when they are inverted.
# @param {TreeNode} root
# @return {TreeNode}
def invert_tree(root)
return nil if root.nil?
root.left, root.right = invert_tree(root.right), invert_tree(root.left)
root
end
An Array serves as the queue: shift takes the next node and << appends its children. Each node's children are swapped with the same parallel assignment, and only the ones that are not nil are queued.
# @param {TreeNode} root
# @return {TreeNode}
def invert_tree(root)
return nil if root.nil?
queue = [root]
until queue.empty?
node = queue.shift
node.left, node.right = node.right, node.left
queue << node.left if node.left
queue << node.right if node.right
end
root
end
Invert a Binary Tree in Dart
2 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.
Return null for an empty subtree; after that check Dart promotes the parameter root to TreeNode. Keep the old left child in a final local, store the inverted right subtree on the left, then the inverted old left subtree on the right.
class Solution {
TreeNode? invertTree(TreeNode? root) {
if (root == null) return null;
final left = root.left;
root.left = invertTree(root.right);
root.right = invertTree(left);
return root;
}
}
A Queue<TreeNode> from dart:collection holds the nodes still to swap. Each pass reads both children into locals, writes them back crossed, and queues the locals that are not null. Testing the locals rather than node.left lets Dart promote them, so no ! is needed.
import 'dart:collection';
class Solution {
TreeNode? invertTree(TreeNode? root) {
if (root == null) return null;
final queue = Queue<TreeNode>()..add(root);
while (queue.isNotEmpty) {
final node = queue.removeFirst();
final left = node.left;
final right = node.right;
node.left = right;
node.right = left;
if (right != null) queue.add(right);
if (left != null) queue.add(left);
}
return root;
}
}
Invert a Binary Tree in Scala
2 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.
The method body is an expression that ends in root, so there is no return at all. When root is not null, keep the old left child in a val, store the inverted right subtree on the left and the inverted old left subtree on the right; an empty tree falls through and comes back as null.
object Solution {
def invertTree(root: TreeNode): TreeNode = {
if (root != null) {
val left = root.left
root.left = invertTree(root.right)
root.right = invertTree(left)
}
root
}
}
A scala.collection.mutable.Queue holds the nodes still to swap, and a while loop drains it: dequeue() the head, swap its two var fields through a temporary, and enqueue the children that are not null. The loop has no closure in it, so nothing here trips Scala 3's non-local-return warning.
import scala.collection.mutable
object Solution {
def invertTree(root: TreeNode): TreeNode = {
if (root != null) {
val queue = mutable.Queue(root)
while (queue.nonEmpty) {
val node = queue.dequeue()
val left = node.left
node.left = node.right
node.right = left
if (node.left != null) queue.enqueue(node.left)
if (node.right != null) queue.enqueue(node.right)
}
}
root
}
}
FAQ for Python
How do I check if two binary trees are mirrors of each other?
Compare them crosswise: def is_mirror(a, b): return a is b if a is None or b is None else a.val == b.val and is_mirror(a.left, b.right) and is_mirror(a.right, b.left). It returns True for [8, 3, 10, 1, 6, 9, 14] and [8, 10, 3, 14, 9, 6, 1], and False for [8, 3, 10] against itself, because a tree is only its own mirror when it is symmetric.
Does inverting change the original tree?
Yes. Both versions swap the children in place and return the same root object, so the original shape is gone. To keep it, build a mirrored copy instead: def mirrored(node): return None if node is None else TreeNode(node.val, mirrored(node.right), mirrored(node.left)). On [5, 2, 9, None, 4] the original still reads [5, 2, 9, None, 4] and the copy reads [5, 9, 2, None, None, 4].
Can I use a stack instead of a queue?
Yes. Replace the deque with a list and popleft() with pop(). That visits nodes depth-first instead of level by level, but every node still gets exactly one swap, so the result is the same: [8, 10, 3, 14, 9, 6, 1] and [5, 9, 2, None, None, 4] for the two examples. The stack holds O(h) nodes at most, still without recursion.
What happens with an empty tree?
Nothing breaks. The recursive version returns None at its first check, and the iterative one starts with an empty queue, skips the loop and returns root, which is None. Read back as a list, the empty tree is [].
Why does the recursive version fail on very deep trees?
Each level adds a Python call frame, and sys.getrecursionlimit() is 1000 by default. A chain of 5,000 nodes that all hang to the left raises RecursionError: maximum recursion depth exceeded. The deque version has no such limit and inverts the same chain. Raising the limit with sys.setrecursionlimit works too, but a loop is the safer fix. The cases here stay within 200 levels, so both versions pass.
FAQ for JavaScript
Why does the recursive invertTree throw RangeError on a deep tree?
Every pending call keeps a frame on V8's call stack, and that stack has a fixed size. On our engine (Node 26) a chain of 5,000 left children inverts fine, a chain of 20,000 throws RangeError: Maximum call stack size exceeded, and the cutoff in between sits roughly around 10,000 frames, moving a little with how warm the JIT is. The level loop has no such ceiling and inverts the 20,000-node chain. The cases here stay within 200 levels, so both versions pass.
Why swap with destructuring instead of two separate assignments?
Two lines like root.left = invertTree(root.right); root.right = invertTree(root.left); read root.left after it was already overwritten. The original left subtree is lost, and the right one is run through the function twice and ends up hanging on both sides: [8, 3, 10, 1, 6, 9, 14] comes out as [8,10,10,14,14,14,14]. The destructuring form evaluates both calls into an array before assigning, which is why it gives [8,10,3,14,9,6,1]. A const tmp works just as well.
Can I use a queue with shift() instead of level arrays?
Yes, and the output is identical: [8,10,3,14,9,6,1] and [5,9,2,null,null,4] for the two examples. The catch is that shift() is defined as moving every remaining element down one slot, so on a wide tree it can cost O(n) per call. Engines optimise some cases, but building a next array per level (or walking the queue with an index) keeps the whole thing linear without relying on that.
How do I get a mirrored copy and keep the original tree?
Both versions above change the nodes in place and hand back the same root. For a copy, build new nodes as you go: const mirrored = (node) => node === null ? null : new TreeNode(node.val, mirrored(node.right), mirrored(node.left));. On [5, 2, 9, null, 4] the original still reads [5,2,9,null,4] and the copy reads [5,9,2,null,null,4]. structuredClone(root) followed by invertTree also works for plain data, but the clone loses the TreeNode prototype.
How do I check whether one tree is the mirror of another?
Compare the outer pair and the inner pair at each step: const mirrors = (p, q) => p === null || q === null ? p === q : p.val === q.val && mirrors(p.left, q.right) && mirrors(p.right, q.left);. Fed the first example and its inverted result, it returns true. Fed [8, 3, 10] twice, it returns false, because only a symmetric tree such as [1, 2, 2] (which returns true) equals its own mirror.
FAQ for TypeScript
Why is the parameter typed TreeNode | null and not just TreeNode?
The empty tree and every missing child are null, and the recursion calls itself on exactly those. With strictNullChecks on, a plain TreeNode parameter would reject invertTree(root.right) at compile time; TreeNode | null admits it and forces the root === null check before root.left is read.
Why walk the queue with an index instead of shift()?
shift() removes the first element and moves every other one down a slot, which can cost O(n) per call on a wide tree. Reading queue[head] and incrementing head is O(1), and the array is thrown away at the end anyway, so keeping the visited nodes in it costs nothing extra.
Why does the two-line swap give the wrong tree?
root.left = invertTree(root.right); root.right = invertTree(root.left); reads root.left after it was overwritten, so the old left subtree is lost and the right one ends up on both sides: [8, 3, 10, 1, 6, 9, 14] comes out as [8, 10, 10, 14, 14, 14, 14]. Destructuring builds the right-hand array first; const left = root.left; before the two assignments works too.
Can the recursive version overflow the stack?
Yes, on a deep enough tree. Each pending call keeps a frame on the JavaScript engine's stack, which has a fixed size, so a chain of tens of thousands of one-sided nodes throws RangeError: Maximum call stack size exceeded. The queue version has no such limit. The cases here stay within 200 levels, so both pass.
How do I return a mirrored copy and keep the original?
Build new nodes instead of swapping: const mirrored = (n: TreeNode | null): TreeNode | null => n === null ? null : new TreeNode(n.val, mirrored(n.right), mirrored(n.left));. On [5, 2, 9, null, 4] the original still reads [5, 2, 9, null, 4] and the copy reads [5, 9, 2, null, null, 4].
FAQ for Java
Why does the recursive version throw StackOverflowError on a deep tree?
Every pending call holds a frame on the current thread stack, and that stack has a fixed size chosen by -Xss when the JVM starts. A tree that leans one way makes the call chain as long as the node count. With this site running Java at -Xss512k, a 5,000-node left chain inverts and a 6,000-node one stops with Exception in thread "main" java.lang.StackOverflowError. You can run the recursion on a thread with a bigger stack, for example new Thread(null, task, "deep", 512L << 20), which got through a 1,000,000-node chain here, but the ArrayDeque loop avoids the question entirely and is the better default for input you do not control. The cases here stay within 200 levels, so both versions pass.
How do I get a mirrored copy in Java and keep the original tree?
Both versions reassign the left and right fields of the objects you pass in, so every reference into that tree now sees the mirror. Build new nodes instead: static TreeNode mirrored(TreeNode node) { if (node == null) { return null; } TreeNode copy = new TreeNode(node.val); copy.left = mirrored(node.right); copy.right = mirrored(node.left); return copy; }. With {5, 2, 9, null, 4}, the original reads [5, 2, 9, null, 4] afterwards and the copy reads [5, 9, 2, null, null, 4]. If TreeNode were a record, its components would be final and neither in-place version would compile; a record tree can only be mirrored by returning new records, as in new TreeNode(n.val(), mirrored(n.right()), mirrored(n.left())).
How can I check in Java that one tree is the mirror of another?
Walk the two trees in step, matching the left child of one against the right child of the other: static boolean isMirror(TreeNode a, TreeNode b) { if (a == null || b == null) { return a == b; } return a.val == b.val && isMirror(a.left, b.right) && isMirror(a.right, b.left); }. Here a == b is a reference check, true only when both are null, and a.val == b.val is safe because val is a primitive int; had it been declared Integer, == would compare object identity and you would need equals. Trees built from {8, 3, 10, 1, 6, 9, 14} and {8, 10, 3, 14, 9, 6, 1} return true; the tree from {8, 3, 10} checked against itself returns false, because 3 and 10 differ and only a symmetric tree is its own mirror.
Should the queue be an ArrayDeque, a LinkedList or a Stack?
ArrayDeque for the queue: it keeps elements in a resizable circular array, which beats allocating a list node per element in LinkedList. Its one restriction is that it rejects null (add(null) throws NullPointerException), hence the guards in the loop. For a depth-first variant, keep the ArrayDeque and switch to push and pop; the legacy Stack class is synchronized and its own docs point to Deque instead. Visiting order changes, but each node is still swapped once, so the output is the same.
Why are the test trees given as Integer values rather than int?
A missing child needs a null, and a primitive int has no such value, so a level-order tree is an Integer[] with null in the empty slots and the numbers autoboxed. Going the other way, new TreeNode(values[i]) unboxes each Integer into the int constructor argument. Unboxing a null throws NullPointerException, which is why a builder tests values[i] != null before creating a node.
FAQ for Go
Can deep recursion crash a Go program on a tall tree?
Only far beyond everyday sizes. A goroutine starts with a small stack that the runtime enlarges as calls pile up, up to a ceiling of 1 GB on 64-bit systems, adjustable with runtime/debug.SetMaxStack. The recursive invertTree gets through a 1,000,000-node chain that leans left. Go past the ceiling and the process stops with fatal error: stack overflow (after debug.SetMaxStack(1 << 20) the runtime first reports goroutine stack exceeds 1048576-byte limit). It is a fatal error, not a panic, so recover never sees it. If the depth of the input is out of your hands, use the slice loop; reading from the end with queue[len(queue)-1] and trimming with queue[:len(queue)-1] turns it into a depth-first stack that produces the same mirror.
Can invertTree be a method on *TreeNode instead of a plain function?
Yes: func (t *TreeNode) Invert() { if t == nil { return }; t.Left, t.Right = t.Right, t.Left; t.Left.Invert(); t.Right.Invert() }. Go lets you call a pointer-receiver method on a nil pointer, so t.Left.Invert() is safe on a leaf and the nil test lives inside the method. The receiver has to be a pointer: with a value receiver, t is a copy of the struct, and swapping the copy leaves the node the caller holds untouched.
How do I test in Go whether two trees are mirror images of each other?
Recurse over both trees together, pairing the left side of one with the right side of the other: func isMirror(a, b *TreeNode) bool { if a == nil || b == nil { return a == b }; return a.Val == b.Val && isMirror(a.Left, b.Right) && isMirror(a.Right, b.Left) }. The pointer comparison a == b settles the nil cases in one line: true when both are nil, false when only one is. Built from []any{8, 3, 10, 1, 6, 9, 14} and []any{8, 10, 3, 14, 9, 6, 1} the pair gives true. Passing the tree from []any{8, 3, 10} as both arguments gives false, since 3 gets compared with 10: only a symmetric tree mirrors itself.
How do I get a mirrored copy and keep the original tree in Go?
Both versions write through the *TreeNode pointers, so the tree the caller passed in is rearranged, and any other variable pointing into it sees the new shape. To leave it alone, allocate fresh nodes: func mirrored(node *TreeNode) *TreeNode { if node == nil { return nil }; return &TreeNode{Val: node.Val, Left: mirrored(node.Right), Right: mirrored(node.Left)} }. For []any{5, 2, 9, nil, 4}, reading both back afterwards shows [5 2 9 nil 4] for the original and [5 9 2 nil nil 4] for the copy. The cost is n new allocations.
Why are the test trees written as []any rather than []int?
Because an int cannot be absent: its zero value 0 is a perfectly good node value, so an []int has nothing to put in an empty child slot. An []any can hold a nil interface there. The builder then gets each number back with the type assertion v.(int), which panics if an entry is not an int. If you would rather stay typed, a []*int (nil pointer = no child) or a sentinel such as math.MinInt does the same job with more ceremony.
FAQ for C#
Is the tuple swap safe, or do I need a temp variable like in Java?
It is safe. (root.left, root.right) = (InvertTree(root.right), InvertTree(root.left)); builds the tuple on the right first, which runs both calls while the fields still hold their old values, and only then assigns the two fields left to right. The Java version has to copy root.left into a local because it assigns one field per statement. If you prefer the explicit form, var left = root.left; root.left = InvertTree(root.right); root.right = InvertTree(left); does the same thing.
Why does the recursive version crash on a very deep tree instead of throwing?
Each pending call takes a frame on the thread stack, and a tree that leans one way makes the chain as long as the node count. When the stack runs out .NET raises StackOverflowException, and unlike other exceptions it cannot be caught: the runtime prints Stack overflow. and ends the process, so no try/catch around the call helps. The main thread gets 1 MB on Windows and whatever ulimit -s says on Linux (8 MB by default), enough for the 200-level cases here but not for an unbounded chain. Run the recursion on new Thread(work, 256 * 1024 * 1024) for a larger stack, or use the Queue<TreeNode> loop, which never touches the call stack.
Does InvertTree change the original tree?
Yes. TreeNode is a class, so both versions reassign left and right on the objects you passed in and return the same root reference; any other variable pointing into that tree now sees the mirror. To keep the original, build new nodes: static TreeNode Mirrored(TreeNode n) => n == null ? null : new TreeNode(n.val, Mirrored(n.right), Mirrored(n.left));. On [5, 2, 9, null, 4] the original still reads [5, 2, 9, null, 4] and the copy reads [5, 9, 2, null, null, 4].
Can I use a Stack<TreeNode> instead of a Queue<TreeNode>?
Yes. Swap Queue<TreeNode> for Stack<TreeNode> and Enqueue/Dequeue for Push/Pop. Nodes are then visited depth-first rather than level by level, but each one is still swapped exactly once, so the result is identical: [8, 10, 3, 14, 9, 6, 1] and [5, 9, 2, null, null, 4] for the two examples. The stack holds at most O(h) nodes while the queue holds up to the widest level, O(w).
How do I check in C# that one tree is the mirror of another?
Walk the two trees crosswise, the left child of one against the right child of the other: static bool IsMirror(TreeNode a, TreeNode b) => a == null || b == null ? a == b : a.val == b.val && IsMirror(a.left, b.right) && IsMirror(a.right, b.left);. Trees built from [8, 3, 10, 1, 6, 9, 14] and [8, 10, 3, 14, 9, 6, 1] return true; [8, 3, 10] checked against itself returns false, since only a symmetric tree is its own mirror.
FAQ for C++
Why does pop() not return the front node?
std::queue::pop() returns void by design: returning the removed element by value could throw while copying after it was already removed, losing it. Read front() first, then call pop(). For a TreeNode* the copy is just a pointer, but the interface is the same for every element type.
Which header does std::swap come from?
Since C++11 it lives in <utility>, which <algorithm>, <vector> and <string> all pull in, so the starter's includes already cover it. The older <algorithm> declaration still works too. std::swap on two TreeNode* exchanges the pointers, not the nodes they point to.
Who frees the nodes?
Nobody needs to here. Inverting only rewires left and right; it allocates nothing and deletes nothing, so the tree the caller built is the tree that comes back. In your own code, owning the children with std::unique_ptr<TreeNode> makes cleanup automatic, and std::swap works on those too.
Can the recursive version crash on a deep tree?
Yes. Every pending call takes a frame on the thread stack, typically 8 MB on Linux, and a tree that leans entirely to one side makes the recursion as deep as the node count. Hundreds of thousands of levels end in a segmentation fault, with no exception to catch. The std::queue version has no such limit. The cases here stay within 200 levels, so both pass.
Should I use nullptr or NULL for the empty tree?
nullptr. It has its own type, std::nullptr_t, which converts to any pointer but never to an integer, so it cannot be picked up by an int overload by mistake. NULL is usually 0 or 0L in C++ and only behaves like a pointer by convention.
FAQ for C
Why is the queue sized to the node count rather than the widest level?
With a plain head / tail pair, tail only grows: every node is written once at a new index and never overwritten, so the array needs one slot per node. A ring buffer that wraps tail with % capacity would get by with the widest level, at the cost of tracking the count separately to tell full from empty.
Why write struct TreeNode everywhere?
In C, a struct's tag lives in its own namespace, so the type is struct TreeNode, not TreeNode. Writing typedef struct TreeNode TreeNode; at the top of your code lets you drop the keyword; the tests work either way.
Do I need to free anything in the recursive version?
No. It only rewrites left and right pointers in nodes the caller already owns; nothing is allocated, so nothing is freed. The iterative version frees its queue before returning, but the nodes themselves stay alive for the caller.
What happens if malloc returns NULL?
Writing queue[tail++] through a NULL pointer is undefined behaviour and usually a segmentation fault. A 3,000-pointer block is 24 KB and will not fail here, but production code checks if (queue == NULL) and reports the error, or falls back to the recursive version.
Can the recursive version overflow the stack?
Yes. Each call keeps a frame on the stack, so a tree that leans to one side recurses once per node, and a deep enough chain crashes with a segmentation fault. C has no exception to catch it. The array queue never recurses. The cases here stay within 200 levels, so both pass.
FAQ for Kotlin
Why does root smart-cast after the null check but root.left does not?
A function parameter is read-only, so once root == null has returned, the compiler knows root is a TreeNode for the rest of the body. left is a var property of a class, and the compiler cannot prove nothing changed it between the check and the use, so if (root.left != null) root.left.val does not compile. Read it into a local val first, or use root.left?.let { ... }, which hands the non-null value to the lambda as it.
How does node.left = node.right.also { node.right = node.left } swap the two children?
also evaluates its receiver first, so the value of node.right is captured, then the lambda runs and sets node.right to the old node.left, and finally also returns the captured value, which is assigned to node.left. It is the usual Kotlin one-line swap without a named temporary; the explicit val left = node.left version in the recursive solution does the same thing and is just as good.
Which ArrayDeque is this, and does it accept null?
Without an import, ArrayDeque is kotlin.collections.ArrayDeque from the standard library, a resizable circular buffer with addLast and removeFirst in amortized O(1). It would accept null if the element type allowed it, but declaring it as ArrayDeque<TreeNode> keeps nulls out at compile time, which is why the children go in through ?.let. java.util.ArrayDeque works too, but it throws NullPointerException on a null element at run time.
Can the recursive version be made tailrec?
No. tailrec only applies when the recursive call is the very last action, and here there are two calls whose results are then assigned to fields, so the compiler would warn that the function is not tail recursive. The recursion depth equals the tree height, at most 200 here, which the JVM stack handles easily. For input whose depth you do not control, the queue version has no depth limit.
Why is the value field declared with backticks around val?
val is a Kotlin keyword, so a property with that name has to be wrapped in backticks wherever it is declared or read, as the starter's TreeNode comment shows. This problem never reads the values, since inverting only moves nodes around, so neither solution touches that field.
FAQ for Rust
Why is the tree an Option<Rc<RefCell<TreeNode>>>?
Option is the empty child, Rc lets more than one owner hold the same node (the caller, a parent, a queue), and RefCell allows mutating a node through those shared handles by checking the borrow rules at run time instead of compile time. That is why a node is changed through node.borrow_mut() and read through node.borrow(). A tree with single ownership could be Option<Box<TreeNode>> and be mutated directly, but this is the shape the harness passes.
Why does std::mem::swap(&mut guard.left, &mut guard.right) not compile?
Each field access through a RefMut goes through its DerefMut impl, and the borrow checker treats every call as borrowing the whole guard mutably, so two of them at once are a double mutable borrow (error E0499). Reborrowing once with let node = &mut *guard; gives a plain &mut TreeNode, and through that the compiler can see node.left and node.right are disjoint fields. Taking both children with take(), as the recursive version does, sidesteps the issue too.
What does take() do here, and why not clone the children?
Option::take moves the value out and leaves None in its place, so the recursive call receives ownership of that subtree handle without an extra reference count. node.left.clone() would work as well, since cloning an Option<Rc<…>> only increments the count, but then the old field still points at the subtree until it is overwritten. take() states the intent: the child is moved to the other side.
Can borrow_mut() panic in these solutions?
It panics with already borrowed: BorrowMutError only if the same RefCell is borrowed twice at once. In the recursive version the parent stays borrowed while its children are inverted, but each child is a different RefCell, so that is fine. A real tree never reaches one node twice; a graph where two parents share a child could, and that would panic.
Why return root at the end instead of the node from if let?
The function takes root by value and gives it back. if let Some(node) = &root only borrows it, and the RefMut lives inside that block, so by the time root is returned every borrow has ended. Returning from inside the block while the guard is alive would not compile, because root would still be borrowed.
FAQ for Swift
Why can a let constant have its left and right changed?
TreeNode is a class, a reference type. guard let root = root and let node = queue[head] fix which object the name refers to, not the object's var properties, so root.left = ... is allowed. Had TreeNode been a struct, the let would make the whole value immutable and the assignment would not compile (and a struct could not contain itself anyway without being boxed).
Is (a, b) = (b, a) a safe way to swap two properties?
Yes. The right-hand tuple is fully built from the current values before either target is assigned, so (node.left, node.right) = (node.right, node.left) swaps them. The same rule is what makes the recursive one-liner correct: both invertTree calls finish before root.left changes. swap(&node.left, &node.right) also works on class properties, but the tuple form is the one usually written.
Why a head index instead of queue.removeFirst()?
Array.removeFirst() shifts every remaining element down, so it costs O(n) per call and turns the loop into O(n²) in the worst case. Reading through an index that only moves forward keeps each step O(1); the price is that visited nodes stay in the array until the method returns, which is the same O(n) memory the tree already uses. A Deque type exists in the separate swift-collections package, not in the standard library.
Do I need import Foundation for this?
No. Optionals, arrays, tuples and classes are all in the Swift standard library. On this site import Foundation adds about 1.5 s of startup to every Run, so leave it out unless you need something only Foundation has.
What happens with a very deep tree in the recursive version?
Each level adds one stack frame, so the depth is the tree height, at most 200 here, which is nowhere near the main thread's stack size. A degenerate tree with hundreds of thousands of levels could crash with a stack overflow, which Swift reports as a signal rather than a catchable error; the queue version has no such limit.
FAQ for PHP
Why does changing $root->left change the caller's tree without a reference parameter?
A PHP object variable holds a handle to the object, and passing it to a function copies the handle, not the object. $root->left = ... therefore writes to the same TreeNode the caller holds. An &$root reference would only matter if the method assigned a different object to $root itself, which neither solution does.
Does [$a->left, $a->right] = [$a->right, $a->left] really swap?
Yes. PHP evaluates the right-hand array literal first, copying both current values into it, and only then assigns its elements to the targets on the left in order. Destructuring has worked with property targets since PHP 7.1, and it reads closer to the idea than a $tmp variable, though both are fine.
Why SplQueue and not array_shift on a plain array?
array_shift removes the first element and renumbers every remaining key, so each call is O(n) and a level-order walk of 3,000 nodes does millions of moves. SplQueue is a doubly linked list with O(1) enqueue and dequeue. A plain array with a read index ($queue[$head++]) and $queue[] = $child is equally fast if you prefer arrays.
What is the difference between ?TreeNode and TreeNode|null?
None for the type checker: ?TreeNode is the nullable shorthand from PHP 7.1 and TreeNode|null is the union type spelling from PHP 8.0. The signature uses ?TreeNode natively and TreeNode|null in the docblock, which is the form documentation tools and IDEs read.
Is there a recursion limit in PHP?
PHP itself sets none; recursion goes until the C stack runs out, or until Xdebug's xdebug.max_nesting_level (256 by default) stops it when that extension is loaded. The recursion depth here is the tree height, at most 200, so the recursive method is safe. For trees whose depth you do not control, the SplQueue loop never grows the stack.
FAQ for Ruby
How does root.left, root.right = b, a swap without a temporary?
In a parallel assignment Ruby evaluates every expression on the right first, then assigns the results to the targets on the left in order. So node.left, node.right = node.right, node.left reads both old children before either setter runs. In the recursive version that means both invert_tree calls finish before root.left is replaced.
What does root.left = x actually call?
attr_accessor :val, :left, :right in TreeNode defines a reader left and a writer left= for each name. root.left = x is a call to root.left=(x), which sets the instance variable @left. Writing left = x without the receiver would instead create a local variable, a common slip in Ruby.
Is Array#shift slow for a queue?
Not in CRuby: shift does not move the remaining elements but advances the start of the array's storage, so it is O(1) amortized, and << is amortized O(1) as well. That makes a plain Array a reasonable queue. Thread::Queue exists too, but it is built for passing work between threads and adds locking you do not need here.
Can I write return unless root instead of return nil if root.nil?
Yes. Only nil and false are falsy in Ruby, and a TreeNode is always truthy, so return unless root returns nil for an empty tree in the same way. The same rule lets queue << node.left if node.left skip a missing child.
Will the recursive version raise SystemStackError?
Only on very deep trees. Each level of recursion is one Ruby method frame, and the depth is the tree height, at most 200 here, far below the thousands of frames the default VM stack allows. A chain much deeper than that could raise SystemStackError: stack level too deep; the queue version does not recurse at all.
FAQ for Dart
Why does root promote to TreeNode but node.left still needs a null check every time?
Dart promotes a local variable or parameter after a null check because nothing else can change it in between. left is a public, mutable field, and a field can be overridden by a getter or changed by other code, so if (node.left != null) queue.add(node.left) is a compile error. Copy the field into a local first, as the queue version does, or write node.left! when you know it is set. Dart 3.2 added promotion for private final fields only, which TreeNode's fields are not.
Why Queue from dart:collection instead of a List with removeAt(0)?
List.removeAt(0) shifts every remaining element down one slot, so each call is O(n). The default Queue is a ListQueue, a circular buffer where add and removeFirst are amortized O(1). The order the nodes are visited in does not change the result, so a List used as a stack with add and removeLast is also fine and needs no import.
What does Queue<TreeNode>()..add(root) mean?
.. is the cascade operator: it calls add(root) on the new queue and then evaluates to the queue itself rather than to the return value of add. It is the same as creating the queue on one line and adding the root on the next.
How do I get a mirrored copy and keep the original tree?
Both solutions reassign the fields of the nodes you pass in. To leave the original alone, build new nodes with the positional constructor: TreeNode? mirrored(TreeNode? n) => n == null ? null : TreeNode(n.val, mirrored(n.right), mirrored(n.left));. Inside the conditional expression n is promoted, so n.val needs no !.
Can the recursion overflow the stack?
The recursion depth is the tree height, at most 200 here, which the Dart VM handles without trouble. A chain tens of thousands of levels deep could throw Stack Overflow, which surfaces as a StackOverflowError; the queue version keeps its work on the heap and has no depth limit.
FAQ for Scala
Why is the node's field called value and not val?
val is a Scala keyword, so a field with that name would have to be written with backticks everywhere. The provided TreeNode takes constructor parameters _value, _left and _right and exposes them as the mutable fields value, left and right. Inverting never reads value, so only left and right appear in the solutions.
Why check for null when Scala has Option?
The provided TreeNode uses null for a missing child, so root.left is either a node or null, never an Option. Wrapping with Option(root.left) turns a null into None and is handy in longer code, but for a single check != null is simpler and allocates nothing.
Can I write if (root == null) return null at the top instead?
Yes. A return directly in the method body is fine in Scala 3; the warning only comes from a return inside a lambda, such as the body of a foreach or a for comprehension, which Scala 3 no longer supports as a non-local return. Wrapping the work in if (root != null) { ... } and ending with root simply avoids return altogether, which is the more common Scala style.
Why a mutable Queue and not the immutable one?
scala.collection.immutable.Queue returns a new queue from every operation: dequeue gives back a tuple of the element and the remaining queue, which you would have to thread through a recursive helper or a var. mutable.Queue changes in place, which fits a while loop. mutable.ArrayDeque works the same way with append and removeHead().
Can the recursive version be annotated with @tailrec?
No. It makes two recursive calls and uses their results in assignments, so neither call is in tail position and @tailrec would be a compile error. That is not a problem here because the depth is the tree height, at most 200; the queue version is the one to use when the depth is unbounded.