Invert Binary Tree

Tree
BFS
DFS

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

Examples

Example 1

Input

root

Output

Example 2

Input

root

Output

Constraints

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

Stuck? Hint 1

Recursively swap left and right children for every node.

Editorial· Swap level by level with a queue

Inverting a tree means mirroring it, as if you held it up to a mirror placed beside it. Everything that was on the left ends up on the right, at every level, not just at the top.

Time O(n)Space O(w)

The full walkthrough and code are part of Premium

Input

Expected Output

Ctrl / ⌘ + Enter

Invert Binary Tree

Tree
BFS
DFS

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

Examples

Example 1

Input

root

Output

Example 2

Input

root

Output

Constraints

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

Stuck? Hint 1

Recursively swap left and right children for every node.

Editorial· Swap level by level with a queue

Inverting a tree means mirroring it, as if you held it up to a mirror placed beside it. Everything that was on the left ends up on the right, at every level, not just at the top.

Time O(n)Space O(w)

The full walkthrough and code are part of Premium

Input

Expected Output

Ctrl / ⌘ + Enter