Implement an AVL Tree with the following operations:

$1.$ Insert: Add a node with a given integer value to the AVL Tree. If the root is

empty, initialize it with the new node. Otherwise, place the new node according to AVL

Tree properties, ensuring that the tree remains balanced by performing necessary

rotations.

$2.$ Search: Print $$TRUE$$ if the given element is found in the tree. Otherwise,

print $$FALSE$.$

$3.$ DFS Traversal: Implement methods for the following Depth$-$First Search $($DFS$)$

traversals and print nodes in their respective order:

o In$-$Order Traversal: Prints the tree in the Left$-$Root$-$Right order.

o Pre$-$Order Traversal: Prints the tree in the Root$-$Left$-$Right order.

o Post$-$Order Traversal: Prints the tree in the Left$-$Right$-$Root order.

You will be given N queries where each query has an integer ID that denotes the operation to be

performed based on the ID values. You need to perform the required operations accordingly.

Input Format:

$$ The first line contains an integer N denoting the number of queries.

$$ The next N lines contain the query input where it reads an Integer ID:

o If ID is $1,$ perform the Insert operation. Read an integer value and insert it

into the AVL Tree.

o If ID is $2,$ perform the Search operation. Read an integer value and check

if it is present in the AVL Tree.

o If ID is $3,$ perform the DFS Traversal operation and print the AVL Tree in

In$-$Order, Pre$-$Order, and Post$-$Order traversals, respectively.

Output Format:

Print the updated AVL Tree on every Traverse Operation.

Sample Test Case:

Input:

$10$

$110$

$15115$

$13$

$17$

$120$

$27$

$28$

$3$

$18$

$3$

Output:

TRUE

FALSE

In$-$Order: $357101520$

Pre$-$Order: $105371520$

Post$-$Order: $375201510$

In$-$Order: $3578101520$

Pre$-$Order: $1053781520$

Post$-$Order: $3875201510$

Explanation:

Here, N$=10$ represents the total number of queries to be executed. The queries are executed in

the following order:

The first line $(10)$ indicates that there are $10$ queries.

The subsequent lines detail each query:

$1.$ Insert $10$: Insert $10$ as the root node. The tree is already balanced$\mathrm{.}2.$ Insert $5$: Add $5$ to the left of $10.$ The tree remains balanced.

$3.$ Insert $15$: Add $15$ to the right of $10.$ The tree remains balanced.

$4.$ Insert $3$: Add $3$ to the left of $5.$ The tree remains balanced.

$5.$ Insert $7$: Add $7$ to the right of $5.$ The tree remains balanced.

$6.$ Insert $20$: Add $20$ to the right of $15.$ The tree remains balanced.

$7.$ Search $7$: The value $7$ is found in the AVL Tree. Output TRUE.

$8.$ Search $8$: The value $8$ is not found in the AVL Tree. Output FALSE.

$9.$ DFS Traversals $($In$-$Order, Pre$-$Order, Post$-$Order$)$:

In$-$Order $($Left$-$Root$-$Right$)$: $357101520$

Pre$-$Order $($Root$-$Left$-$Right$)$: $105371520$

Post$-$Order $($Left$-$Right$-$Root$)$: $375201510$

$10.$ Insert $8$: Add $8$ to the right of $7.$ This causes an imbalance, so a left rotation is

performed at node $7.$ The tree is rebalanced.

$11.$ DFS Traversals $($Updated$)$:

In$-$Order: $3578101520$

Pre$-$Order: $1053871520$

Post$-$Order: $3785201510$ in C$++$ program code