Invert Binary Tree

Invert Binary Tree is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.

Problem statement

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

Example 1:

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

Example 2:

Input: root = [2,1,3] Output: [2,3,1]

Example 3:

Input: root = [] Output: []

Constraints:

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

- -100 <= Node.val <= 100

Topics and companies

Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree.

Reported in interviews at Microsoft, Amazon, Google, Facebook, eBay, Paypal.

How to practise Invert Binary Tree on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(h) space.

Open Invert Binary Tree in the code editor, or read the Invert Binary Tree editorial for a worked solution with its approach and complexity analysis.

Where Invert Binary Tree sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Recursive Preorder Traversal subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Invert Binary Tree

Other problems that use the same Recursive Preorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

• Binary Tree Paths — Easy, same subpattern
• Construct Binary Tree from Preorder and Inorder Traversal — Medium, same subpattern
• Flatten Binary Tree to Linked List — Medium, same subpattern
• Same Tree — Easy, same subpattern
• Smallest String Starting From Leaf — Medium, same subpattern
• Symmetric Tree — Easy, same subpattern