Insertion in AVL Tree
Ninja has to implement an ‘AVL_TREE’ from scratch.

He is given ‘N’ values, representing the values of nodes to be inserted. Ninja has to insert these values into the ‘AVL_TREE’ and return its root after inserting all the nodes.

Note: An ‘AVL_TREE’ is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

For example:

Input Format

The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains an integer ‘N’ which represents the number of nodes in the tree. The next line of each test case contains ‘N’ single space-separated integers, representing the value of each node.

Output Format :

For each test case, print the ‘AVL_TREE’ after inserting all the nodes in level order. Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Insertion in AVL Tree

Ninja has to implement an ‘AVL_TREE’ from scratch.

He is given ‘N’ values, representing the values of nodes to be inserted. Ninja has to insert these values into the ‘AVL_TREE’ and return its root after inserting all the nodes.

Note: An ‘AVL_TREE’ is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

For example:

Input Format

The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’ which represents the number of nodes in the tree.

The next line of each test case contains ‘N’ single space-separated integers, representing the value of each node.

Output Format :

For each test case, print the ‘AVL_TREE’ after inserting all the nodes in level order. 


Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^4
1 <= ‘DATA’ <= 10^5

Time Limit: 1 second

Accepted Answer

The question asks to implement an AVL_TREE from scratch and insert given values into it.

AVL_TREE is a self-balancing binary search tree
The height difference between left and right subtrees of all nodes should not be more than one
Implement the AVL_TREE data structure and insertion algorithm
Return the root of the AVL_TREE after inserting all the nodes

Accepted Answer

Brute Force

We have to implement ‘AVL_TREE’ from scratch and we know ‘AVL_TREE’ follows the ‘BST’ properties. So first, we insert a new node into ‘AVL_TREE’ according to the ‘BST’ properties.

‘BST’ property:

DATA(left) < DATA(root) < DATA(right) for every node.

And the difference between heights of left and right subtrees cannot be more than one for all nodes.

After inserting the new node in our tree according to the ‘BST’ properties our tree may be unbalanced (i.e the difference between the height of left and right subtree more than one for a node).

So for making this tree balance we have to perform some operations:

Left Rotation.
Right Rotation.

Here, T1, T2, and T3 are the subtrees of the trees.

For re-balancing the tree by performing appropriate rotations we have 4 possible cases that need to be handled.

Left Left case
Left Right case
Right Right case
Right Left case

Left-Left case:

Left-Right case:

Right-Right case:

Right-Left case:

Here is the algorithm:

First, we insert a new node into our tree according to the standard ‘BST’ insertion.
Starting from the root, we traverse the whole tree and find the unbalanced node.
Then we re-balance the tree by performing appropriate rotations. We have 4 possible cases as discussed above that need to be handled.

Space Complexity: O(logn)Explanation:

O(log(N)) where ‘N’ is the number of nodes in the ‘AVL_TREE’.

Because first, we insert the new node according to ‘BST’ insertion, and then if required we are re-balancing the tree as well. The space occupied by the recursion stack is equal to the height of the tree. Since our tree is balanced so the height of the tree is log(N). Hence the space complexity is O(log(N)).

Time Complexity: O(nlogn)Explanation:

O(N * log(N)) where ‘N’ is the number of nodes in the ‘AVL_TREE’.

Because first, we insert the new node according to ‘BST’ insertion which takes O(log(N)) time. If after insertion our tree is unbalanced then we are performing rotations according to one of the above 4 cases which takes constant time. We are doing this amount of work for every node. So the overall time complexity is O(N * log(N)).

Java (SE 1.8)

/*

	Time complexity: O(N * log(N))

	Space complexity: O(log(N))



	Where N denotes the number of nodes in the Avl tree.

*/



public class Solution {



	public static TreeNode rightRotation(TreeNode y) {



		TreeNode x = y.left;

		TreeNode t2 = x.right;



		x.right = y;

		y.left = t2;



		y.height = Math.max(height(y.left), height(y.right)) + 1;

		x.height = Math.max(height(x.left), height(x.right)) + 1;



		return x;



	}



	public static TreeNode leftRotation(TreeNode x) {



		TreeNode y = x.right;

		TreeNode t2 = y.left;



		y.left = x;

		x.right = t2;



		x.height = Math.max(height(x.left), height(x.right)) + 1;

		y.height = Math.max(height(y.left), height(y.right)) + 1;



		return y;



	}



	public static int height(TreeNode root) {

		if (root == null) {

			return 0;

		}



		return root.height;

	}



	public static int getBalanceFactor(TreeNode root) {

		if (root == null) {

			return 0;

		}



		return height(root.left) - height(root.right);

	}



	public static TreeNode insertInAvltree(TreeNode root, int data) {



		// Normal BST insertion.

		if (root == null) {

			return new TreeNode<>(data);

		}



		if (data < root.data) {

			root.left = insertInAvltree(root.left, data);

		} else if (data > root.data) {

			root.right = insertInAvltree(root.right, data);

		} else {

			return root;

		}



		// Update height of every node of the tree.

		root.height = 1 + Math.max(height(root.left), height(root.right));



		// Checking if the tree is balanced or not.

		int balanceFactor = getBalanceFactor(root);



		// If the tree is unbalanced then we have 4 cases to handle.



		// 1. Left Left case.

		if (balanceFactor > 1 && data < root.left.data) {

			return rightRotation(root);

		}



		// 2. Right Right case.

		if (balanceFactor < -1 && data > root.right.data) {

			return leftRotation(root);

		}



		// 3. Left Right case.

		if (balanceFactor > 1 && data > root.left.data) {

			root.left = leftRotation(root.left);

			return rightRotation(root);

		}



		// 4. Right Left case.

		if (balanceFactor < -1 && data < root.right.data) {

			root.right = rightRotation(root.right);

			return leftRotation(root);

		}



		return root;



	}



	public static TreeNode insertionInAvlTree(int allNodeValues[], int n) {

		TreeNode root = null;

		for (int i = 0; i < n; i++) {

			root = insertInAvltree(root, allNodeValues[i]);

		}

		return root;

	}

}

C++ (g++ 5.4)

/*

	Time complexity: O(N * log(N))

	Space complexity: O(log(N))



	Where N denotes the number of nodes in the Avl tree.

*/



int height(TreeNode* root) {

	if (root == NULL) {

		return 0;

	}



	return root -> height;

}



TreeNode* rightRotation(TreeNode* y) {



	TreeNode* x = y -> left;

	TreeNode* t2 = x -> right;



	x -> right = y;

	y -> left = t2;



	y -> height = max(height(y -> left), height(y -> right)) + 1;

	x -> height = max(height(x -> left), height(x -> right)) + 1;



	return x;



}



TreeNode* leftRotation(TreeNode* x) {



	TreeNode* y = x -> right;

	TreeNode* t2 = y -> left;



	y -> left = x;

	x -> right = t2;



	x -> height = max(height(x -> left), height(x -> right)) + 1;

	y -> height = max(height(y -> left), height(y -> right)) + 1;



	return y;



}



int getBalanceFactor(TreeNode* root) {

	if (root == NULL) {

		return 0;

	}



	return height(root -> left) - height(root -> right);

}



TreeNode* insertInAvltree(TreeNode* root, int data) {



	// Normal BST insertion.

	if (root == NULL) {

		return new TreeNode(data);

	}



	if (data < root -> data) {

		root -> left = insertInAvltree(root -> left, data);

	} else if (data > root -> data) {

		root -> right = insertInAvltree(root -> right, data);

	} else {

		return root;

	}



	// Update height of every node of the tree.

	root -> height = 1 + max(height(root -> left), height(root -> right));



	// Checking if the tree is balanced or not.

	int balanceFactor = getBalanceFactor(root);



	// If the tree is unbalanced then we have 4 cases to handle.



	// 1. Left Left case.

	if (balanceFactor > 1 && data < root -> left -> data) {

		return rightRotation(root);

	}



	// 2. Right Right case.

	if (balanceFactor < -1 && data > root -> right -> data) {

		return leftRotation(root);

	}



	// 3. Left Right case.

	if (balanceFactor > 1 && data > root -> left -> data) {

		root -> left = leftRotation(root -> left);

		return rightRotation(root);

	}



	// 4. Right Left case.

	if (balanceFactor < -1 && data < root -> right -> data) {

		root -> right = rightRotation(root -> right);

		return leftRotation(root);

	}



	return root;



}



TreeNode* insertionInAvlTree(vector& allNodeValues, int n) {



	TreeNode* root = NULL;

	for (int i = 0; i < n; i++) {

		root = insertInAvltree(root, allNodeValues[i]);

	}

	return root;



}

Python (3.5)

'''
	Time complexity: O(N * log(N))
	Space complexity: O(log(N))

	Where N denotes the number of nodes in the Avl tree.
'''

class TreeNode:
    
    def __init__(self, data):
        self.data = data
        self.height = 1
        self.right = None
        self.left = None


def rightRotation(y):
    
    x = y.left
    t2 = x.right
    
    x.right = y
    y.left = t2
    
    y.height = max(getHeight(y.left), getHeight(y.right)) + 1
    x.height = max(getHeight(x.left), getHeight(x.right)) + 1
    
    return x


def leftRotation(x):
    
    y = x.right
    t2 = y.left
    
    y.left = x
    x.right = t2
    
    x.height = max(getHeight(x.left), getHeight(x.right)) + 1
    y.height = max(getHeight(y.left), getHeight(y.right)) + 1
    
    return y


def getHeight(root):
    
    if root == None:
        return 0
        
    return root.height
    
        
def getBalanceFactor(root):
    
    if root == None:

        return 0
        
    return getHeight(root.left) - getHeight(root.right)

    
def insertInAvlTree(root, data):
    
    # Normal BST insertion.
    if root == None:
        return TreeNode(data)
        
    if data < root.data:
        root.left = insertInAvlTree(root.left, data)
        
    elif data > root.data:
        root.right = insertInAvlTree(root.right, data)
        
    else:
        return root
        
    # Update height of every node of the tree.
    root.height = 1 + max(getHeight(root.left), getHeight(root.right))
    
    # Checking if the tree is balanced or not.
    balanceFactor = getBalanceFactor(root)
    
    # If the tree is unbalanced then we have 4 cases to handle.
    
    # 1. Left Left case.
    if balanceFactor > 1 and data < root.left.data:
        return rightRotation(root)
        
    # 2. Right Right case.
    if balanceFactor < -1 and data > root.right.data:
        return leftRotation(root)
        
    # 3. Left Right case.
    if balanceFactor > 1 and data > root.left.data:
        root.left = leftRotation(root.left)
        return rightRotation(root)
        
    # 4. Right Left case.
    if balanceFactor < -1 and data < root.right.data:
        root.right = rightRotation(root.right)
        return leftRotation(root)
        
    return root


def insertionInAvlTree(allNodeValues, n):
    
    root = None
    for i in range(n):
        root = insertInAvlTree(root, allNodeValues[i])
        
    return root