What is the time complexity of Invert Binary Tree?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Invert Binary Tree?

This problem uses Tree, Depth-First Search, Breadth-First Search, Binary Tree. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Invert Binary Tree?

Insight 1: Recursive approach is ideal for traversing and manipulating a tree's structure. The problem naturally lends itself to recursion because inverting a subtree is independent of inverting other subtrees. Insight 2: The base case for the recursion is an empty subtree (null or None). When a subtree is empty, nothing needs to be inverted, and the function can simply return.

Which companies ask LeetCode 226. Invert Binary Tree in interviews?

This problem is frequently asked at Oracle, Ozon.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Invert Binary Tree - LeetCode 226 Solution

Q: How to solve Invert Binary Tree?

The provided solutions use a recursive approach. The `invertTree` function takes the root of the tree as input. If the root is `null` (or `None`), it means the tree is empty, so it returns `null`. Otherwise, it recursively inverts the left and right subtrees, then swaps the left and right children of the current node. The swapped children, which are now the inverted subtrees, are assigned back to the left and right of the current node, and the inverted root is returned.

Invert Binary Tree - Complete Solution Guide

Invert Binary Tree is LeetCode problem 226, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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

Detailed Explanation

The problem asks you to invert a given binary tree. Inverting a binary tree means swapping the left and right children of every node in the tree. The input is the root node of the binary tree, and the output is the root node of the inverted binary tree. The input can be an empty tree (represented by `null` or `None`), a single node, or a tree with multiple nodes. Constraints limit the number of nodes and the range of node values.

Solution Approach

The provided solutions use a recursive approach. The `invertTree` function takes the root of the tree as input. If the root is `null` (or `None`), it means the tree is empty, so it returns `null`. Otherwise, it recursively inverts the left and right subtrees, then swaps the left and right children of the current node. The swapped children, which are now the inverted subtrees, are assigned back to the left and right of the current node, and the inverted root is returned.

Step-by-Step Algorithm

Step 1: Check if the root node is `null` (or `None`). If it is, return `null` (or `None`) because an empty tree is already inverted.
Step 2: Recursively call `invertTree` on the left subtree and assign the result to a temporary variable (or directly swap in-place).
Step 3: Recursively call `invertTree` on the right subtree and assign the result to another temporary variable (or directly swap in-place).
Step 4: Swap the left and right children of the current node using simultaneous assignment (e.g., `root.left, root.right = root.right, root.left`).
Step 5: Return the modified root node.

Key Insights

Insight 1: Recursive approach is ideal for traversing and manipulating a tree's structure. The problem naturally lends itself to recursion because inverting a subtree is independent of inverting other subtrees.
Insight 2: The base case for the recursion is an empty subtree (null or None). When a subtree is empty, nothing needs to be inverted, and the function can simply return.
Insight 3: The order of swapping left and right children and the recursive calls is crucial. Swapping them first ensures the correct inversion; recursive calls happen *after* the swap.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(h)

Topics

This problem involves: Tree, Depth-First Search, Breadth-First Search, Binary Tree.

Companies

Asked at: Oracle, Ozon.

Invert Binary Tree | LeetCode 226

Easy

Tree Depth-First Search Breadth-First Search Binary Tree

Time: O(n)Space: O(h)

Solution Code

Available in:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 226: Invert Binary Tree - Detailed explanation and solution approaches.

Topics

Tree Depth-First Search Breadth-First Search Binary Tree

Companies

OracleOzon

Stats

Difficulty:Easy

Languages:4

Companies:2

Problem #:226

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Check if the root node is `null` (or `None`). If it is, return `null` (or `None`) because an empty tree is already inverted.
2
Step 2: Recursively call `invertTree` on the left subtree and assign the result to a temporary variable (or directly swap in-place).
3
Step 3: Recursively call `invertTree` on the right subtree and assign the result to another temporary variable (or directly swap in-place).
4
Step 4: Swap the left and right children of the current node using simultaneous assignment (e.g., `root.left, root.right = root.right, root.left`).
5
Step 5: Return the modified root node.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(h)

📝

Why?

The recursive calls create a call stack whose depth is proportional to the height of the tree. Each node is processed in constant time. Therefore, the time complexity is linear in the number of nodes. The space used is proportional to the maximum depth of the recursion, which is the height of the tree.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Approach (BFS)

Use a queue to perform a Breadth-First Search (BFS). Iteratively process nodes level by level, swapping left and right children at each node.

Time: O(n)Space: O(w), where w is the maximum width of the tree (number of nodes at the widest level). In worst case O(n) for a complete tree.

Trade-offs: The iterative approach using BFS may use more space in the case of a wide tree compared to the recursive approach. However, it avoids the potential stack overflow issues associated with very deep recursive calls.

Iterative Approach (DFS)

Use a stack to perform a Depth-First Search (DFS). Simulates recursion without explicit recursion calls

Time: O(n)Space: O(h), where h is the height of the tree.

Trade-offs: Similar time complexity to recursion, but avoids potential issues with deep recursion and offers better control over stack management.

✨

Key Insights

1Insight 1: Recursive approach is ideal for traversing and manipulating a tree's structure. The problem naturally lends itself to recursion because inverting a subtree is independent of inverting other subtrees.
2Insight 2: The base case for the recursion is an empty subtree (null or None). When a subtree is empty, nothing needs to be inverted, and the function can simply return.
3Insight 3: The order of swapping left and right children and the recursive calls is crucial. Swapping them first ensures the correct inversion; recursive calls happen *after* the swap.

📚

Key Terms Explained

For Students

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Empty tree (root is `null` or `None`). The solution handles this gracefully by returning `null` immediately, preventing further processing.
Edge case 2: Tree with only one node. The function will swap the left and right (which are both `null`), effectively leaving the tree unchanged, which is the correct behavior.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting the base case (`if root == null`). This leads to infinite recursion and a stack overflow.

✗Common mistake 2: Incorrect order of swapping and recursive calls. Swapping must happen *before* the recursive calls to ensure the correct inversion. Doing it the other way around will lead to an incorrect result.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: In image processing, inverting a tree structure representing an image's organization might be needed for specific transformations or mirror effects.

🏦Real-world scenario 2: In game development, inverting a tree representing a game world's structure could be used to create a mirrored version of a level or scenario.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Most tree problems can be solved recursively. The base case is usually a null node. Think about what information needs to flow up vs down the tree.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Not handling null nodes properly. Always check if the current node exists before accessing its children.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 17, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

How do I choose between recursive and iterative tree traversal?

Use recursive traversal for cleaner code when stack depth isn't a concern (tree height < ~1000). Use iterative with explicit stack for very deep trees to avoid stack overflow. Iterative is also preferred when you need fine-grained control over the traversal process.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Invert Binary Tree"?

For this easy-level Tree problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?