## Algorithm

Problem Name: Data Structures - Self Balancing Tree

In this HackerRank in Data Structures - Self Balancing Tree solutions

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.

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.

Sample Output

``````    3
/  \
2    5
/ \
4   6
``````

Explanation

After inserting 6 in the tree. the tree becomes:

``````    3 (Balance Factor = -2)
/  \
2    4 (Balance Factor = -2)
\
5 (Balance Factor = -1)
\
6 (Balance Factor = 0)
``````

Balance Factor of nodes 3 and 4 is no longer in the range [-1,1]. We need to perform a rotation to balance the tree. This is the right right case. We perform a single rotation to balance the tree.

After performing the rotation, the tree becomes :

``````                              3 (Balance Factor = -1)
/   \
(Balance Factor = 0) 2     5 (Balance Factor = 0)
/ \
(Balance Factor = 0)4   6 (Balance Factor = 0)
``````

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
node* newAvlTreeNode(int data);
int heightOfSubtree(node *nod);
int maxVal(int a, int b);
node *leftRotate(node *x);
node* rightRotate(node *y);
int getBalance(node *Nod);

node* insert(node* root,int val)
{
if (root == NULL)
return  newAvlTreeNode(val);

if (val  <  root -> val)
root->left = insert(root->left,val );
else if (val > root->val)
root->right = insert(root->right,val );

root->ht = 1 + maxVal(heightOfSubtree(root->left), heightOfSubtree(root->right));

//Get the balance factor of parent node
int balance = getBalance(root);

if (balance > 1 && val  <  root->left->val)
return rightRotate(root);

// Right Right Case
if (balance < -1 && val > root->right->val)
return leftRotate(root);

// Left Right Case
if (balance > 1 && val > root->left->val)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}

// Right Left Case
if (balance  <  -1 && val < root->right->val)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}

node* rightRotate(node *y)
{
node* x = y->left;
node* T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->ht = maxVal(heightOfSubtree(y->left), heightOfSubtree(y->right)) + 1;
x->ht = maxVal(heightOfSubtree(x->left), heightOfSubtree(x->right)) + 1;

// Return new root
return x;
}

node *leftRotate(node *x)
{
node *y = x->right;
node *T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

//  Update heights
x->ht = maxVal(heightOfSubtree(x->left), heightOfSubtree(x->right)) + 1;
y->ht = maxVal(heightOfSubtree(y->left), heightOfSubtree(y->right)) + 1;

// Return new root
return y;
}

int getBalance(node *Nod)
{
if (Nod == NULL)
return 0;
return heightOfSubtree(Nod->left) - heightOfSubtree(Nod->right);
}

int maxVal(int a,int b)
{
return (a > b) ? a : b;
}

node* newAvlTreeNode(int data)
{
// Allocate memory for new node
node* treeNode = (node*)malloc(sizeof(node));

// Assign data to this node
treeNode->val = data;

// Initialize left and right children as NULL
treeNode->left = NULL;
treeNode->right = NULL;
treeNode->ht = 0;
return(treeNode);
}

int heightOfSubtree(node *nod)
{
if (nod == NULL)
return -1;
return nod->ht;
}
``````
Copy The Code &

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
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
}
``````
Copy The Code &

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const pr = console.log;

class AVLNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
this.height = 1;
this.cnt = 1;
}
}

class AVLTree {
constructor() {
this.root = null;
}
getHeight(node) {
return node != null ? node.height : 0;
}
getBalance(node) {
return node != null ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
}
LR(z) {
let y = z.right;
let T2 = y.left;
y.left = z;
z.right = T2;
z.height = 1 + Math.max(this.getHeight(z.left), this.getHeight(z.right));
y.height = 1 + Math.max(this.getHeight(y.left), this.getHeight(y.right));
return y;
}
RR(z) {
let y = z.left;
let T3 = y.right;
y.right = z
z.left = T3
z.height = 1 + Math.max(this.getHeight(z.left), this.getHeight(z.right));
y.height = 1 + Math.max(this.getHeight(y.left), this.getHeight(y.right));
return y;
}
insert(v) {
this.root = this.insertUtil(this.root, v);
}
insertUtil(node, v) {
if (node == null) {
return new AVLNode(v);
} else if (v  <  node.val) {
node.left = this.insertUtil(node.left, v);
} else if (v > node.val) {
node.right = this.insertUtil(node.right, v);
} else {
node.cnt++;
return node;
}
node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
let bal = this.getBalance(node);
if (bal > 1 && v  <  node.left.val) return this.RR(node);
if (bal > 1 && v > node.left.val) {
node.left = this.LR(node.left);
return this.RR(node);
}
if (bal  <  -1 && v > node.right.val) return this.LR(node);
if (bal < -1 && v < node.right.val) {
node.right = this.RR(node.right);
return this.LR(node);
}
return node;
}
remove(v) {
this.root = this.removeUtil(this.root, v);
}
removeUtil(node, v) {
if (node == null) {
return node;
} else if (v  <  node.val) {
node.left = this.removeUtil(node.left, v);
} else if (v > node.val) {
node.right = this.removeUtil(node.right, v);
} else {
if (node.cnt > 1) {
node.cnt--;
return node;
}
if (node.left == null) {
let tmp = node.right;
node = null;
return tmp;
} else if (node.right == null) {
let tmp = node.left;
node = null;
return tmp;
}
let tmp = this.findMin(node.right);
node.val = tmp.val;
node.right = this.removeUtil(node.right, tmp.val);
}
if (node == null) return node;
node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
let bal = this.getBalance(node);
if (bal > 1 && this.getBalance(node.left) >= 0) return this.RR(node);
if (bal  <  -1 && this.getBalance(node.right) <= 0) return this.LR(node);
if (bal > 1 && this.getBalance(node.left) < 0) {
node.left = this.LR(node.left);
return this.RR(node);
}
if (bal  <  -1 && this.getBalance(node.right) > 0) {
node.right = this.RR(node.right);
return this.LR(node);
}
return node;
}
FindFirstOf(value) {
let node = this.root, res = null;
while (node != null) {
if (value  <  node.val) {
node = node.left;
} else if (value > node.val) {
node = node.right;
} else {
res = node;
node = node.left;
}
}
return res;
}
FindLastOf(value) {
let node = this.root, res = null;
while (node != null) {
if (value  <  node.val) {
node = node.left;
} else if (value > node.val) {
node = node.right;
} else {
res = node;
node = node.right;
}
}
return res;
}
maxx() {
let node = this.findMax(this.root);
return node == null ? null : node.val;
}
minx() {
let node = this.findMin(this.root);
return node == null ? null : node.val;
}
findMin(node) {
return node == null || node.left == null ? node : this.findMin(node.left);
}
findMax(node) {
return node == null || node.right == null ? node : this.findMax(node.right);
}
preOrder_DFS() {
let d = [];
this.dfs(this.root, d);
return d;
}
dfs(node, d) {
if (!node) return;
d.push(node.val);
this.dfs(node.left, d);
this.dfs(node.right, d);
}
}

let tree;
const solve = (n, a, v) => {
tree = new AVLTree();
for (const x of a) tree.insert(x);
a.push(v);
tree.insert(v);
op(a);
};

const op = (a) => {
let res = [], orderPrint = [], m = new Map();
for (const x of a) {
// FindFirstOf FindLastOf both works
let node = tree.FindFirstOf(x), bal = tree.getBalance(node), s = `\${x}(BF=\${bal})`;
m.set(x, s);
orderPrint.push([x, s])
}
orderPrint.sort((x, y) => x[0] - y[0]);
pr(orderPrint.map(x => x[1]).join(" "));
let preorder = tree.preOrder_DFS();
for (const x of preorder) res.push(m.get(x));
pr(res.join(" "));
};

const main = () => {
const readLine = () => input[currentLine++];
const ni = () => readLine() - '0';
const nas = () => readLine().split(" ");
const nai = () => nas().map(Number);
const nal = () => nas().map(BigInt);
let input = '', currentLine = 0;
process.stdin.on('data', (stdin) => input += stdin)
process.stdin.on('end', () => {
input = input.split('\n');
let n = ni(), a = nai(), v = ni();
solve(n, a, v);
});
};

main()
``````
Copy The Code &