Implement a program for Binary Tree, Binary Search Tree (BST), and AVL Tree.
Implement programs for Binary Tree, Binary Search Tree (BST), and AVL Tree. There will be certain operations you need to implement for the given trees. The operations will be selected using some key inputs, mentioned below.
| Key (Query Identifier) | Input | Functionality |
|---|---|---|
| B | N A1 A2 A3 ... AN | Constructing BST: |
| N: N operations including insertion/deletion. | ||
| Ai: Operand. | ||
| If Ai is positive => Insert in BST. | ||
| Else if Ai is negative => Remove it from BST (If input is -5, delete 5 if it exists). | ||
| Else if Ai is 0 => No operation. | ||
| A | N A1 A2 A3 ... AN | Constructing AVL: |
| N: N operations including insertion/deletion. | ||
| Ai: Operand. | ||
| If Ai is positive => Insert in AVL. | ||
| Else if Ai is negative => Remove it from AVL. | ||
| Else if Ai is 0 => No operation. | ||
| I | A1 (A1 will be positive value) | Insert node A1 in the current existing tree. If the tree is empty, add the element as the first node of a BST. |
| R | A1 (A1 will be positive value) | Remove the node A1 from the current existing tree. If the element is not there or the tree is empty, do nothing. |
| F | X | Find X in the current tree. Print “Yes” if X is in the tree, “No” if X is not. If X is negative or 0, do nothing. |
| L | - | Print the number of leaves present in the tree. |
| N | - | Print the number of total nodes in the tree. |
| Q | - | Print In-order traversal of the tree. |
| W | - | Print Pre-order traversal of the tree. |
| E | - | Print Post-order traversal of the tree. |
| H | - | Print the height of the tree (a single node will have height 0). |
| M | - | Print the boundary traversal of the tree (clockwise). |
| C | A1 A2 | Print the lowest common ancestor of nodes A1 and A2. If either A1 or A2 does not exist, print -1. If A1 == A2, print A1. |
| Z | N A1 A2 A3 ... AN B1 B2 B3 ... BN | Given pre-order (A1...AN) and in-order (B1...BN) sequences, print the post-order sequence of the tree. |
| Y | N A1 A2 A3 ... AN B1 B2 B3 ... BN | Given post-order (A1...AN) and in-order (B1...BN) sequences, print the pre-order sequence of the tree. |
| K | - | Remove the entire tree if it exists. |
| D | - | End operations in the current test case and move to the next test case (if any). |