Skip to content

Volume ITechnology

4.14.1 — Invert Binary Tree ​

LeetCode 226 · Easy · ★ Blind 75

The problem ​

You are given the root of a binary tree. Turn it into its mirror image, so that every node's left child and right child swap places. Return the root.

A binary tree is a set of nodes where each node holds a value and has at most two children, called left and right. The top node is the root. A node with no children is a leaf. 4.13.1 builds trees from the ground up.

     4                4
   /   \            /   \
  2     7    →     7     2
 / \   / \        / \   / \
1   3 6   9      9   6 3   1

The tree has up to 100 nodes. It may be empty.

What the problem is really asking ​

Hold the tree up to a mirror. The whole tree flips: what was on the left is now on the right, at every level, all the way down.

Look at it node by node. At the root, 2 and 7 swap. Then, inside what used to be the left side, 1 and 3 swap. Inside what used to be the right side, 6 and 9 swap. So the real question is: at each node, swap its two children, and do the same thing for every node below.

The key idea for every tree problem ​

A tree is built from smaller trees. A node's left child is the root of a smaller tree, called its left subtree, and the same goes for the right. That means a problem about a tree can almost always be solved by:

  1. doing a small job at this node, and
  2. asking the same function to solve the subtrees.

A function that calls itself on smaller pieces is called recursive. The most useful habit for tree problems is to trust the recursive call. Do not trace it all the way down in your head. Assume that invertTree(node.left) correctly mirrors everything below node.left, and only ask: "what does this node have to do?"

Here, this node has to swap its two children. That is all.

The brute force ​

There is no slower "obvious" method worth writing here. You must touch every node at least once to swap its children, so any correct answer takes at least O(n) time, and the recursive answer already does exactly that.

The solution ​

python
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:                                  # (1)
            return None

        root.left, root.right = root.right, root.left  # (2)
        self.invertTree(root.left)                     # (3)
        self.invertTree(root.right)

        return root                                    # (4)
ts
function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;                              // (1)

  [root.left, root.right] = [root.right, root.left];   // (2)
  invertTree(root.left);                               // (3)
  invertTree(root.right);

  return root;                                         // (4)
}

Line by line ​

(1) The base case. If there is no node, there is nothing to mirror. This line is what makes the recursion stop. Every call eventually reaches a missing child, and those calls return straight away. It also handles an empty tree, and a node with only one child, because the missing child is just None.

(2) Swap the two children of this node. In Python, a, b = b, a swaps two values in one line. Both right-hand values are read first, then both are assigned, so nothing is lost. TypeScript does the same with [a, b] = [b, a].

(3) Mirror both subtrees. We trust these two calls to mirror everything below. Note that after line (2), root.left is the old right child. That does not matter. Both subtrees get mirrored either way.

(4) Return the root, which is still the same node, now with its whole tree mirrored.

The swap and the recursive calls can go in either order. You could mirror both subtrees first and swap afterwards. Both work, because swapping two children and mirroring what is inside each child are separate jobs that do not affect each other.

Trace ​

Take the tree 4 with children 2 and 7, where 2 has children 1 and 3, and 7 has children 6 and 9. Each row is one call.

Call onSwap at this nodeThen calls on
42 ↔ 7, so left = 7, right = 27, then 2
76 ↔ 9, so left = 9, right = 69, then 6
9no children to swap (both None)None, None → return
6no childrenreturn
21 ↔ 3, so left = 3, right = 13, then 1
3no childrenreturn
1no childrenreturn

The result is 4 with children 7 (with 9, 6) and 2 (with 3, 1), which is the mirrored tree.

Complexity, derived ​

Time. Every node is visited exactly once, and each visit does one swap. So the time is O(n).

Space. Each recursive call waits on the call stack until its children's calls finish. The deepest chain of waiting calls is as long as the tree is tall. We call that the tree's height, h. So the extra memory is O(h).

How big is h? For a balanced tree, where the two sides of every node have roughly the same size, h is about \log_2 n. For a tree that has become a straight line, where every node has only one child, h is n. So say "O(h)", not "O(\log n)". The log only holds if the tree is balanced, and nothing here promises that.

Edge cases ​

  • Empty tree. Line (1) returns None.
  • One node. Its two children are both None. Swapping them changes nothing.
  • A node with one child. The child moves to the other side, and the missing side becomes None.
  • A long chain. Works, but the recursion is n deep. Python stops at about 1,000 nested calls by default, which this problem's 100-node limit never reaches.

The version without recursion ​

Any recursive tree walk can be written with your own list of nodes still to visit. Using a queue, where nodes leave in the order they arrived, visits the tree level by level. That is called a breadth-first walk.

python
from collections import deque

def invertTree(self, root):
    if not root:
        return None
    queue = deque([root])                   # nodes still to visit
    while queue:
        node = queue.popleft()              # take the oldest waiting node
        node.left, node.right = node.right, node.left
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return root

There is one reason to know this version. Recursion keeps its waiting calls on the call stack, which is small. A tree shaped like a long chain can make it overflow. Your own queue lives in the much larger general memory, so it does not have that limit.

Variations you will meet ​

Every problem in this chapter starts from the same question: what does this node do, and what does it need from its children?

  • Symmetric Tree. Is a tree its own mirror image? Compare the left subtree with the right subtree, walking them in opposite directions at the same time.
  • Maximum Depth, Same Tree, Diameter. The same shape, with a different small job at each node. They follow in this chapter.

What the interviewer will push on ​

"Does the order of the swap and the recursive calls matter?" No. Swapping a node's children and mirroring inside each child are independent jobs.

"What is the space complexity?" O(h) for the call stack. Say "height", and add that it is O(\log n) only for a balanced tree.

"Can you do it without recursion?" Yes, with a queue or a stack of nodes to visit.

One thing to volunteer: say that you are trusting the recursive call, and only deciding what this one node does. That habit is what makes every later tree problem manageable.

Next: 4.14.2 Maximum Depth of Binary Tree. The same recursion, now passing a number back up instead of changing the tree.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet