Self Balancing Tree

Problem Statement :

```An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.

We define balance factor for each node as :

balanceFactor = height(left subtree) - height(right subtree)
The balance factor of any node of an AVL tree is in the integer range [-1,+1]. If after any modification in the tree, the balance factor becomes less than −1 or greater than +1, the subtree rooted at this node is unbalanced, and a rotation is needed.

(https://en.wikipedia.org/wiki/AVL_tree)

You are given a pointer to the root of an AVL tree. You need to insert a value into this tree and perform the necessary rotations to ensure that it remains balanced.

Input Format

You are given a function,

node *insert(node * root,int new_val)
{

}
'node' is defined as :

struct node
{
int val;            //value
struct node* left;  //left child
struct node* right; //right child
int ht;             //height of the node
} node;
You only need to complete the function.

Note: All the values in the tree will be distinct. Height of a Null node is -1 and the height of the leaf node is 0.

Output Format

Insert the new value into the tree and return a pointer to the root of the tree. Ensure that the tree remains balanced.

Sample Input

3
/  \
2    4
\
5
The value to be inserted is 6.```

Solution :

```                            ```Solution in C :

In C++ :

/* Node is defined as :
typedef struct node
{
int val;
struct node* left;
struct node* right;
int ht;
} node; */

node * insert(node * T,int x)
{
if (T == NULL)
{
T = (node*)malloc(sizeof(node));
T->val = x;
T->left = NULL;
T->right = NULL;
}
else if (x > T->val)
{
T->right = insert_hidden(T->right, x);
if (BF_hidden(T) == -2)
{
if (x > T->right->val)
{
T = RR_hidden(T);
}
else
{
T = RL_hidden(T);
}
}
}
else if (x < T->val)
{
T->left = insert_hidden(T->left, x);
if (BF_hidden(T) == 2){
if (x < T->left->val)
{
T = LL_hidden(T);
}
else
{
T = LR_hidden(T);
}
}
}
T->ht = ht_hidden(T);
return(T);

}

In Java :

/* Class node is defined as :
class Node
int val;   //Value
int ht;      //Height
Node left;   //Left child
Node right;   //Right child

*/

static Node insert(Node root,int val) {
Node newNode = new Node();
newNode.val = val;
newNode.ht = 0;
newNode.left = null;
newNode.right = null;

if (root==null) {
root = newNode;
} else {
root=avlinsert(newNode, root);
}

return root;
}

// return height of tree rooted at x
static public int height(Node x) {
if (x == null) return -1;
else return x.ht;
}

static public Node rotatewithleft(Node c) {
Node p;  // left child of c

p = c.left;
c.left = p.right;
p.right = c;

c.ht = Math.max(height(c.left), height(c.right)) + 1;
p.ht = Math.max(height(p.left), height(p.right)) + 1;

return p;
}

static public Node rotatewithright(Node c) {
Node p;  // right child of c

p = c.right;
c.right = p.left;
p.left = c;

c.ht = Math.max(height(c.left), height(c.right)) + 1;
p.ht = Math.max(height(p.left), height(p.right)) + 1;

return p;
}

static public Node doublerotatewithleft(Node c) {
Node tmp;

c.left = rotatewithright(c.left);
tmp = rotatewithleft(c);

return tmp;
}

static public Node doublerotatewithright(Node c) {
Node tmp;

c.right = rotatewithleft(c.right);
tmp = rotatewithright(c);

return tmp;
}

static public Node avlinsert(Node newNode, Node par) {
Node newpar = par;  // root of subtree par

if (newNode.val < par.val)  {
if (par.left == null) {
par.left = newNode;  //attach new node as leaf
}
else {
par.left = avlinsert(newNode, par.left);   // branch left
if ((height(par.left) - height(par.right)) == 2) {
if (newNode.val < par.left.val) {
newpar=rotatewithleft(par);
} else {
newpar=doublerotatewithleft(par);
} //else
} //if
} // else
} // if
else if (newNode.val > par.val) { // branch right
if (par.right == null) {
par.right = newNode;   // attach new node as leaf
} else {
par.right = avlinsert(newNode, par.right);  // branch right
if ((height(par.right) - height(par.left)) == 2) {
if (newNode.val > par.right.val) {
newpar=rotatewithright(par);
} //if
else {
newpar=doublerotatewithright(par);
} //else
} //if
} //else
}  // else if

// Update the height, just in case

if ((par.left == null) && (par.right != null))
par.ht = par.right.ht + 1;
else if ((par.right == null) && (par.left != null))
par.ht = par.left.ht + 1;
else
par.ht = Math.max(height(par.left), height(par.right)) + 1;

return newpar; // return new root of this subtree
}```
```

Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing