Problem

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

OR

Change a tree so that the roles of the left and right pointers are swapped at every node.

Example

Example 1 Given binary tree

     1
   /   \
  2     3
 / \   / \
4   5 6   7

invert and return

     1
   /   \
  3     2
 / \   / \
7   6 5   4

root=[1,2,3,4,5,6,7]
output: [1,3,2,7,6,5,4]

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f**k off.

Solution

The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. Alternately, if you do not want to change the tree nodes, you may construct and return a new mirror tree based on the original tree.

Method 1 - Recursion without Separate Helper Function

This is how the recursion will work:

  • If the root is None, return None.
  • For each node, swap its left and right children.
  • Recursively invert the left and right subtrees.
  • Return the root.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
class Solution{
	public TreeNode invertTree(TreeNode root) {
		if (root == null) {
			return null;
		}
	
		TreeNode temp = root.left;
		root.left = root.right;
		root.right = temp;
	
		invertTree(root.left);
		invertTree(root.right);
		return root;
	}
}
Python
class Solution:
    def invertTree(self, root: Optional['TreeNode']) -> Optional['TreeNode']:
        if root is None:
            return None
        
        # Swap the left and right children
        root.left, root.right = root.right, root.left
        
        # Recursively invert the left and right subtrees
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        return root

Complexity

  • ⏰ Time complexity: O(n) where n is the number of nodes in the tree. Each node is visited once.
  • 🧺 Space complexity: O(h) where h is the height of the tree. In the worst case of a skewed tree, the recursion stack will go up to the height of the tree, which is O(n) in the worst case.

Method 2 - Recursion using helper function

Code

Java
class Solution{
	public TreeNode invertTree(TreeNode root) {
		if (root != null) {
			dfs(root);
		}
	
		return root;
	}
	
	private void dfs(TreeNode p) {
		TreeNode temp = p.left;
		p.left = p.right;
		p.right = temp;
	
		if (p.left != null) {
			dfs(p.left);
		}
	
		if (p.right != null) {
			dfs(p.right);
		}
	}
}

Method 3 - Iterative Using Queue and BFS

Here is the iterative solution using BFS(or level order traversal).

Code

Java
class Solution {
	public TreeNode invertTree(TreeNode root) {
		LinkedList<TreeNode> queue = new LinkedList<TreeNode> ();
	
		if (root != null) {
			queue.add(root);
		}
	
		while (!queue.isEmpty()) {
			TreeNode p = queue.poll();
			if (p.left != null) {
				queue.add(p.left);
			}
			if (p.right != null) {
				queue.add(p.right);
			}
	
			TreeNode temp = p.left;
			p.left = p.right;
			p.right = temp;
		}
	
		return root;
	}
}

Method 4 - Iterative Using Stack and DFS

Code

Java
class Solution {
	public TreeNode invertTree(TreeNode root) {
		if (root==null)
			return;
	
		Stack<TreeNode> stk = new Stack<>();
		stk.push(root);
		while (!stk.empty()) {
			Node curr = stk.pop();
	
			// Swap the children
			Node temp = curr.right;
			curr.right = curr.left;
			curr.left = temp;
	
			// Push the children on the stack
			if (curr.right!=null) {
				stk.push(curr.right);
			}
	
			if (curr.left!=null) {
				stk.push(curr.left);
			}
		}
		return root;
	}
}