# Invert Binary Tree

## Problem Statement

Invert a binary tree.

## Testcase

```
Input:
         4
       /   \
      2     7
     / \   / \
    1   3 6   9
    
Output:
         4
       /   \
      7     2
     / \   / \
    9   6 3   1
```

## Prerequisite Knowledge

### Binary Tree

A binary tree is a tree data structure in which each parent node has a maximum of two child nodes.

![Binary Tree](https://3540593164-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9DtKfC4RdOdz3G4SbS%2F-M9IUzygA5SjGwfhbWQY%2F-M9InIbOGzrfaW_c1qPM%2Fbinarytree.png?alt=media\&token=2d86eb8a-905a-46ae-aafe-05f18aa902b8)

### Level Order Traversal

Level Order Tree Traversal is also known as Breadth-First Traversal. In this type of traversal, we traverse through and print the nodes at each level before traversing further down the tree, as shown in the example.

![Level Order Traversal: 1->2->3->4->5](https://3540593164-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9DtKfC4RdOdz3G4SbS%2F-M9J8GBeuhqa7QegsIy6%2F-M9J9QzEJnDT9IUJj8Ri%2Flevel_order_traversal.png?alt=media\&token=4b38d746-567a-4653-9ace-c8e2246a5e8b)

## Problem Explanation

### Inverting a Binary Tree

An inverted binary tree is a mirror image of the original binary tree. At every level of the binary tree, we must swap the left and right nodes in order to obtain an inverted image of the binary tree.

![Original Tree vs. Inverted Tree](https://3540593164-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9DtKfC4RdOdz3G4SbS%2F-M9IUzygA5SjGwfhbWQY%2F-M9Is0n4waAsxHuwv2Ny%2FScreenshot%20from%202020-06-08%2017-48-50.png?alt=media\&token=1841174c-acda-4fb5-a5d1-1d6cd5becd9f)

## Algorithm

### Recursive Approach

1. If the tree is empty, return NULL as the inverse of an empty tree is an empty tree.
2. Recursively traverse through the left and right branches of the tree in a depth-first manner.
3. When the leaf nodes have been reached, set the respective left and right pointers to NULL.
4. Backtrack through each level and swap the left and right sub-trees.
5. The process is completed when the root node is reached.

{% hint style="info" %}
Time Complexity: O(n)
{% endhint %}

## Code

```cpp
TreeNode* invertTree(TreeNode* root) {
    // Inverse of an empty tree is an empty tree
    if (root == NULL) {
        return NULL;
    }
        
    // Recursively invert each subtree starting from the root
    TreeNode *right = invertTree(root->right);
    TreeNode *left = invertTree(root->left);
            
    // Exchange the pointers to the left and right nodes
    root->left = right;
    root->right = left;
        
    return root;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-1/invert-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.