# Invert Tree - Amazon Top Interview Questions

### Problem Statement :

```Given a binary tree root, invert it so that its left subtree and right subtree are swapped and the children are recursively inverted.

Constraints

n ≤ 100,000 where n is the number of nodes in root

Example 1

Input

root = [0, [2, null, null], [9, [7, null, null], [12, null, null]]]

Output

[0, [9, [12, null, null], [7, null, null]], [2, null, null]]```

### Solution :

```                        ```Solution in C++ :

Tree* solve(Tree* root) {
if (root == nullptr) {
return root;
}
queue<Tree*> q;
q.push(root);
while (!q.empty()) {
Tree* curr = q.front();
q.pop();
// swapping left and right nodes
Tree* temp = curr->left;
curr->left = curr->right;
curr->right = temp;
if (curr->left != nullptr) {
q.push(curr->left);
}
if (curr->right != nullptr) {
q.push(curr->right);
}
}
return root;
}```
```

```                        ```Solution in Java :

import java.util.*;

/**
* public class Tree {
*   int val;
*   Tree left;
*   Tree right;
* }
*/
class Solution {
public Tree solve(Tree root) {
return mirror(root);
}
static Tree mirror(Tree root) {
if (root == null)
return null;
Tree left = mirror(root.left);
Tree right = mirror(root.right);
root.left = right;
root.right = left;
return root;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, root):
if root:
dq = deque([root])
while dq:
node = dq.popleft()
node.left, node.right = node.right, node.left
if node.left:
dq.append(node.left)
if node.right:
dq.append(node.right)
return root```
```

## Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

## Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

## Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your \$inOrder* func

## Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

## Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

## Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F