Invert Binary Tree

Easy · Trees · Explanation and code example

Iterative DFS

How it works

Iterative DFS inverts a binary tree using an explicit stack instead of recursion.
The idea is the same as recursive DFS:

  • Visit a node.
  • Swap its left and right children.
  • Continue the process for its children.

But instead of the call stack, we use our own stack data structure.

The process is:

  1. Push the root into the stack.
  2. Pop the top node, swap its children.
  3. Push its children onto the stack (if they exist).
  4. Continue until the stack is empty.

This simulates the recursive DFS in an iterative manner and works well when recursion depth may be too large.

Steps

  1. If root is null, return null.
  2. Initialize a stack with root.
  3. While stack is not empty:
    • Pop a node.
    • Swap its left and right pointers.
    • If the left child exists, push it to the stack.
    • If the right child exists, push it to the stack.
  4. Return the root.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Things to watch for

Not Handling Null Root

Forgetting to check for a null root causes null pointer exceptions. Always return null immediately if the root is null.

Using Wrong References After Swap

After swapping, root.left now points to what was previously root.right. When recursing, make sure you're using the correct references for the swapped children.

Modifying While Traversing Incorrectly

In iterative approaches, ensure you push children to the stack after swapping, not before. Pushing before the swap means you're adding references to positions that will change.

Python code example

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        stack = [root]
        while stack:
            node = stack.pop()
            node.left, node.right = node.right, node.left
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return root

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        stack<TreeNode*> stack;
        stack.push(root);
        while (!stack.empty()) {
            TreeNode* node = stack.top();
            stack.pop();
            swap(node->left, node->right);
            if (node->left) stack.push(node->left);
            if (node->right) stack.push(node->right);
        }
        return root;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations