Invert Binary Tree

Problem Statement

Given the root of a binary tree, invert the tree, and return its root.

Inverting a binary tree means swapping the left and right child nodes of every node in the tree.

What to notice first

• Every node in the tree must have its left and right children swapped.
• The tree structure remains the same, only the direction of children changes.
• This is a simple problem that teaches fundamental tree traversal techniques.

Examples

Input	Output	Explanation
[4,2,7,1,3,6,9]	[4,7,2,9,6,3,1]	All left-right children are swapped at each node
[2,1,3]	[2,3,1]	Left and right children of root are swapped
[]	[]	Empty tree remains empty

Constraints

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Real-World Applications

Where this pattern appears

• Mirror image processing — create a mirror/flipped version of a hierarchical structure like organizational charts.
• Game tree reflection — flip the decision tree in game AI for symmetry analysis.
• UI layout mirroring — invert left/right layout for right-to-left (RTL) language support.
• Data structure optimization — balance tree traversal patterns for hardware cache efficiency.

Complexity Comparison

Approach	Time	Space	Type	Best When
DFS Recursive	O(n)	O(h)	Elegant	General case — simple and intuitive
BFS Iterative	O(n)	O(w)	Queue-based	Level-by-level processing preferred

h = height of tree, w = max width at any level

Which approach should you learn first?

• Pick DFS Recursive if you want the cleanest, most readable solution.
• Pick BFS Iterative if you prefer avoiding recursion or need level-order processing.

Most Elegant

DFS Recursive

O(n) time · O(h) space

No Recursion

BFS Iterative

O(n) time · O(w) space

Approach 1: DFS Recursive (Recommended)

★ Recommended

Recursively visit each node, swap its left and right children, then continue the process for its subtrees.

The elegance of this approach lies in its simplicity: three lines of code (swap + two recursive calls) handle any tree size.

⏱ Time O(n) Visit each node once 💾 Space O(h) Call stack depth

Step-by-step Example

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

Original tree:       4           Inverted tree:       4
                   /   \                            /   \
                  2     7                          7     2
                 / \   / \                        / \   / \
                1   3 6   9                      9   6 3   1

Step	Action
1	Visit node 4: swap its children (2 ↔ 7)
2	Recurse on new left child (7): swap (6 ↔ 9)
3	Recurse on new right child (2): swap (1 ↔ 3)
4	Return to leaf nodes (no children to swap)

Animated walkthrough

How the DFS recursive solution inverts the tree

Use Next or Autoplay to watch the left-right swap operation at each node, starting from the root and moving down the tree.

Back Autoplay Next Reset

Step 1 of 5 Target: invert

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function invertTreeDFS(root):
    if root is null:
        return null

    swap(root.left, root.right)
    invertTreeDFS(root.left)
    invertTreeDFS(root.right)

    return root

Solution Code

Python

invert_binary_tree_dfs.py

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def invert_tree_dfs(root: Optional[TreeNode]) -> Optional[TreeNode]:
    """
    DFS Recursive approach to invert a binary tree.
    Recursively swap left and right children for each node.

    Time Complexity: O(n) - visit each node once
    Space Complexity: O(h) - recursion stack depth (h = height)
    """
    if root is None:
        return None

    # Swap left and right children
    root.left, root.right = root.right, root.left

    # Recursively invert left and right subtrees
    invert_tree_dfs(root.left)
    invert_tree_dfs(root.right)

    return root


# Test case
if __name__ == "__main__":
    # Create tree:     1
    #                /   \
    #               2     3
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)

    invert_tree_dfs(root)

    # Expected:        1
    #                /   \
    #               3     2
    print(f"Root: {root.val}")  # 1
    print(f"Left: {root.left.val}, Right: {root.right.val}")  # 3, 2

C++

invert_binary_tree_dfs.cpp

#include <iostream>
#include <memory>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    /**
     * DFS Recursive approach to invert a binary tree.
     * Recursively swap left and right children for each node.
     *
     * Time Complexity: O(n) - visit each node once
     * Space Complexity: O(h) - recursion stack depth (h = height)
     */
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        // Swap left and right children
        swap(root->left, root->right);

        // Recursively invert left and right subtrees
        invertTree(root->left);
        invertTree(root->right);

        return root;
    }
};

int main() {
    // Create tree:     1
    //                /   \
    //               2     3
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    Solution sol;
    sol.invertTree(root);

    // Expected:        1
    //                /   \
    //               3     2
    cout << "Root: " << root->val << endl;  // 1
    cout << "Left: " << root->left->val << ", Right: " << root->right->val << endl;  // 3, 2

    return 0;
}

Java

invert_binary_tree_dfs.java

import java.util.LinkedList;
import java.util.Queue;

public class invert_binary_tree_dfs {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
        }
    }

    static class Solution {
        /**
         * DFS Recursive approach to invert a binary tree.
         * Recursively swap left and right children for each node.
         *
         * Time Complexity: O(n) - visit each node once
         * Space Complexity: O(h) - recursion stack depth (h = height)
         */
        public TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return null;
            }

            // Swap left and right children
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;

            // Recursively invert left and right subtrees
            invertTree(root.left);
            invertTree(root.right);

            return root;
        }
    }

    public static void main(String[] args) {
        // Create tree:     1
        //                /   \
        //               2     3
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        Solution sol = new Solution();
        sol.invertTree(root);

        // Expected:        1
        //                /   \
        //               3     2
        System.out.println("Root: " + root.val);  // 1
        System.out.println("Left: " + root.left.val + ", Right: " + root.right.val);  // 3, 2
    }
}

JavaScript

invert_binary_tree_dfs.js

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

/**
 * DFS Recursive approach to invert a binary tree.
 * Recursively swap left and right children for each node.
 *
 * Time Complexity: O(n) - visit each node once
 * Space Complexity: O(h) - recursion stack depth (h = height)
 *
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if (root === null) {
        return null;
    }

    // Swap left and right children
    [root.left, root.right] = [root.right, root.left];

    // Recursively invert left and right subtrees
    invertTree(root.left);
    invertTree(root.right);

    return root;
};

// Test case
if (require.main === module) {
    // Create tree:     1
    //                /   \
    //               2     3
    const root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);

    invertTree(root);

    // Expected:        1
    //                /   \
    //               3     2
    console.log(`Root: ${root.val}`);  // 1
    console.log(`Left: ${root.left.val}, Right: ${root.right.val}`);  // 3, 2
}

module.exports = invertTree;

Rust

invert_binary_tree_dfs.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * DFS Recursive approach to invert a binary tree.
 * Recursively swap left and right children for each node.
 *
 * Time Complexity: O(n) - visit each node once
 * Space Complexity: O(h) - recursion stack depth (h = height)
 */
pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    root.and_then(|node| {
        let mut n = node.borrow_mut();

        // Swap left and right children
        let temp = n.left.take();
        n.left = n.right.take();
        n.right = temp;

        // Recursively invert left and right subtrees
        drop(n);
        invert_tree(node.borrow_mut().left.take());
        invert_tree(node.borrow_mut().right.take());

        Some(node)
    })
}

fn main() {
    // Create tree:     1
    //                /   \
    //               2     3
    let root = Some(Rc::new(RefCell::new(TreeNode {
        val: 1,
        left: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
        right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
    })));

    let result = invert_tree(root);

    // Expected:        1
    //                /   \
    //               3     2
    if let Some(node) = result {
        let n = node.borrow();
        println!("Root: {}", n.val);  // 1
        if let Some(left) = &n.left {
            if let Some(right) = &n.right {
                println!(
                    "Left: {}, Right: {}",
                    left.borrow().val,
                    right.borrow().val
                );  // 3, 2
            }
        }
    }
}

Go

invert_binary_tree_dfs.go

package main

import (
  "fmt"
)

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

/**
 * DFS Recursive approach to invert a binary tree.
 * Recursively swap left and right children for each node.
 *
 * Time Complexity: O(n) - visit each node once
 * Space Complexity: O(h) - recursion stack depth (h = height)
 */
func invertTree(root *TreeNode) *TreeNode {
  if root == nil {
    return nil
  }

  // Swap left and right children
  root.Left, root.Right = root.Right, root.Left

  // Recursively invert left and right subtrees
  invertTree(root.Left)
  invertTree(root.Right)

  return root
}

func main() {
  // Create tree:     1
  //                /   \
  //               2     3
  root := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 2,
    },
    Right: &TreeNode{
      Val: 3,
    },
  }

  invertTree(root)

  // Expected:        1
  //                /   \
  //               3     2
  fmt.Printf("Root: %d\n", root.Val)  // 1
  fmt.Printf("Left: %d, Right: %d\n", root.Left.Val, root.Right.Val)  // 3, 2
}

Approach 2: BFS Iterative

🎯 Interview Favourite

Use a queue to visit nodes level by level, swapping children at each node without using the recursion call stack.

This approach is useful when you want explicit control over traversal order or need to avoid stack overflow on very deep trees.

⏱ Time O(n) Visit each node once 💾 Space O(w) Queue width

Step-by-step Example

Input: root = [2,1,3]

After processing:

Step	Queue	Current Node	Action
1	[2]	2	Dequeue 2, swap (1 ↔ 3), enqueue [3, 1]
2	[3, 1]	3	Dequeue 3, no children, continue
3	[1]	1	Dequeue 1, no children, continue
4	[]	-	Queue empty, done

Pseudocode

function invertTreeBFS(root):
    if root is null:
        return root

    queue = Queue()
    queue.enqueue(root)

    while queue is not empty:
        node = queue.dequeue()
        swap(node.left, node.right)

        if node.left is not null:
            queue.enqueue(node.left)
        if node.right is not null:
            queue.enqueue(node.right)

    return root

Solution Code

Python

invert_binary_tree_bfs.py

from typing import Optional
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def invert_tree_bfs(root: Optional[TreeNode]) -> Optional[TreeNode]:
    """
    BFS Iterative approach to invert a binary tree.
    Uses a queue to visit nodes level by level, swapping children.

    Time Complexity: O(n) - visit each node once
    Space Complexity: O(w) - w = max width of tree (nodes at widest level)
    """
    if root is None:
        return root

    queue = deque([root])

    while queue:
        node = queue.popleft()

        # Swap left and right children
        node.left, node.right = node.right, node.left

        # Add children to queue for processing
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return root


# Test case
if __name__ == "__main__":
    # Create tree:     1
    #                /   \
    #               2     3
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)

    invert_tree_bfs(root)

    # Expected:        1
    #                /   \
    #               3     2
    print(f"Root: {root.val}")  # 1
    print(f"Left: {root.left.val}, Right: {root.right.val}")  # 3, 2

C++

invert_binary_tree_bfs.cpp

#include <iostream>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    /**
     * BFS Iterative approach to invert a binary tree.
     * Uses a queue to visit nodes level by level, swapping children.
     *
     * Time Complexity: O(n) - visit each node once
     * Space Complexity: O(w) - w = max width of tree (nodes at widest level)
     */
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return root;
        }

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            // Swap left and right children
            swap(node->left, node->right);

            // Add children to queue for processing
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }

        return root;
    }
};

int main() {
    // Create tree:     1
    //                /   \
    //               2     3
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    Solution sol;
    sol.invertTree(root);

    // Expected:        1
    //                /   \
    //               3     2
    cout << "Root: " << root->val << endl;  // 1
    cout << "Left: " << root->left->val << ", Right: " << root->right->val << endl;  // 3, 2

    return 0;
}

Java

invert_binary_tree_bfs.java

import java.util.LinkedList;
import java.util.Queue;

public class invert_binary_tree_bfs {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
        }
    }

    static class Solution {
        /**
         * BFS Iterative approach to invert a binary tree.
         * Uses a queue to visit nodes level by level, swapping children.
         *
         * Time Complexity: O(n) - visit each node once
         * Space Complexity: O(w) - w = max width of tree (nodes at widest level)
         */
        public TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return root;
            }

            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);

            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();

                // Swap left and right children
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;

                // Add children to queue for processing
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }

            return root;
        }
    }

    public static void main(String[] args) {
        // Create tree:     1
        //                /   \
        //               2     3
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        Solution sol = new Solution();
        sol.invertTree(root);

        // Expected:        1
        //                /   \
        //               3     2
        System.out.println("Root: " + root.val);  // 1
        System.out.println("Left: " + root.left.val + ", Right: " + root.right.val);  // 3, 2
    }
}

JavaScript

invert_binary_tree_bfs.js

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

/**
 * BFS Iterative approach to invert a binary tree.
 * Uses a queue to visit nodes level by level, swapping children.
 *
 * Time Complexity: O(n) - visit each node once
 * Space Complexity: O(w) - w = max width of tree (nodes at widest level)
 *
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if (root === null) {
        return root;
    }

    const queue = [root];
    let front = 0;

    while (front < queue.length) {
        const node = queue[front++];

        // Swap left and right children
        [node.left, node.right] = [node.right, node.left];

        // Add children to queue for processing
        if (node.left !== null) {
            queue.push(node.left);
        }
        if (node.right !== null) {
            queue.push(node.right);
        }
    }

    return root;
};

// Test case
if (require.main === module) {
    // Create tree:     1
    //                /   \
    //               2     3
    const root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);

    invertTree(root);

    // Expected:        1
    //                /   \
    //               3     2
    console.log(`Root: ${root.val}`);  // 1
    console.log(`Left: ${root.left.val}, Right: ${root.right.val}`);  // 3, 2
}

module.exports = invertTree;

Rust

invert_binary_tree_bfs.rs

use std::cell::RefCell;
use std::rc::Rc;
use std::collections::VecDeque;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * BFS Iterative approach to invert a binary tree.
 * Uses a queue to visit nodes level by level, swapping children.
 *
 * Time Complexity: O(n) - visit each node once
 * Space Complexity: O(w) - w = max width of tree (nodes at widest level)
 */
pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    if root.is_none() {
        return root;
    }

    let mut queue = VecDeque::new();
    queue.push_back(root.clone());

    while let Some(Some(node)) = queue.pop_front() {
        let mut n = node.borrow_mut();

        // Swap left and right children
        let temp = n.left.take();
        n.left = n.right.take();
        n.right = temp;

        // Add children to queue for processing
        if let Some(left) = n.left.take() {
            queue.push_back(Some(left));
        }
        if let Some(right) = n.right.take() {
            queue.push_back(Some(right));
        }
    }

    root
}

fn main() {
    // Create tree:     1
    //                /   \
    //               2     3
    let root = Some(Rc::new(RefCell::new(TreeNode {
        val: 1,
        left: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
        right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
    })));

    let result = invert_tree(root);

    // Expected:        1
    //                /   \
    //               3     2
    if let Some(node) = result {
        let n = node.borrow();
        println!("Root: {}", n.val);  // 1
        if let Some(left) = &n.left {
            if let Some(right) = &n.right {
                println!(
                    "Left: {}, Right: {}",
                    left.borrow().val,
                    right.borrow().val
                );  // 3, 2
            }
        }
    }
}

Go

invert_binary_tree_bfs.go

package main

import (
  "fmt"
)

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

/**
 * BFS Iterative approach to invert a binary tree.
 * Uses a queue to visit nodes level by level, swapping children.
 *
 * Time Complexity: O(n) - visit each node once
 * Space Complexity: O(w) - w = max width of tree (nodes at widest level)
 */
func invertTree(root *TreeNode) *TreeNode {
  if root == nil {
    return root
  }

  queue := make([]*TreeNode, 0)
  queue = append(queue, root)

  for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]

    // Swap left and right children
    node.Left, node.Right = node.Right, node.Left

    // Add children to queue for processing
    if node.Left != nil {
      queue = append(queue, node.Left)
    }
    if node.Right != nil {
      queue = append(queue, node.Right)
    }
  }

  return root
}

func main() {
  // Create tree:     1
  //                /   \
  //               2     3
  root := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 2,
    },
    Right: &TreeNode{
      Val: 3,
    },
  }

  invertTree(root)

  // Expected:        1
  //                /   \
  //               3     2
  fmt.Printf("Root: %d\n", root.Val)  // 1
  fmt.Printf("Left: %d, Right: %d\n", root.Left.Val, root.Right.Val)  // 3, 2
}

Common mistakes

Watch for these pitfalls

• Forgetting to swap before recursing — make sure the swap happens at the start, before processing children.
• Only processing one subtree — remember to recursively invert both left and right subtrees.
• Returning the wrong node — return the modified root, not one of its children.
• In BFS: forgetting to add children to the queue before dequeuing the next node.

Related Problems

• Symmetric Tree ↗ Easy #101
• Same Tree ↗ Easy #100
• Binary Tree Postorder Traversal ↗ Easy #145
• Binary Tree Preorder Traversal ↗ Medium #144

Interview Tips

Key trade-offs to discuss

• Why DFS over BFS? Cleaner code, works well for most trees, and matches the tree’s natural recursive structure. Use unless you have a specific reason to avoid recursion.
• Why BFS? Explicit control, avoids deep recursion (good for very deep trees), and enables level-order processing if needed.
• Space complexity nuance: For balanced trees, both are O(log n) due to tree shape. For skewed trees, DFS could approach O(n) with deep recursion, while BFS adapts to tree width.
• Follow-up — Flatten to linked list: A natural extension combining inversion with other tree transformations.
• Follow-up — Spiral level order: Combine BFS with direction reversal for zigzag traversal.

← Previous
#225 Implement Stack using Queues Next
#227 Basic Calculator II →