Given a AVL tree and N values to be inserted in the tree. Write a function to insert a given value into the tree.
Example 1:
N = 3
Values to be inserted = {5,1,4}
Input:      
Value to be inserted = 5
Output:
    5
Input :      
Value to be inserted = 1
Output:
    5
   /
  1
Input :      
Value to be inserted = 4
Output:
  5                     4
 /   LR rotation       / \
1   ----------->      1   5
 \
 4
Your Task:  
You dont need to read input or print anything. Complete the function insertToAVL() which takes the root of the tree and the value of the node to be inserted as input parameters and returns the root of the modified tree.
Note:
The tree will be checked after each insertion. 
If it violates the properties of balanced BST, an error message will be printed followed by the inorder traversal of the tree at that moment.
If instead all insertions are successful, inorder traversal of tree will be printed.
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(height of tree)
Constraints:
1 ≤ N ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3

''' structure of tree node:

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

'''

class Solution:
    def insertToAVL(self, root, key):
        # add key to AVL (if it is not present already)
        # return root node


Solutions:
class Solution:

	def getHeight(self, root):
		if not root:
			return 0
		return root.height

	def leftrotate(self, root):
		node = root.right
		temp = node.left
		node.left = root
		root.right = temp
		root.height = 1 + max(self.getHeight(root.left), self.getHeight(temp))
		node.height = 1 + max(self.getHeight(root), self.getHeight(node.right))
		return node

	def rightrotate(self, root):
		node = root.left
		temp = node.right
		node.right = root
		root.left = temp
		root.height = 1 + max(self.getHeight(root.right), self.getHeight(temp))
		node.height = 1 + max(self.getHeight(root), self.getHeight(node.left))
		return node

	def insertToAVL(self, root, key):
		if not root:
			return Node(key)
		if key < root.data:
			root.left = self.insertToAVL(root.left, key)
		elif key > root.data:
			root.right = self.insertToAVL(root.right, key)
		root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
		balance = self.getHeight(root.left) - self.getHeight(root.right)
		if balance > 1 and key < root.left.data:
			return self.rightrotate(root)
		if balance > 1 and key > root.left.data:
			root.left = self.leftrotate(root.left)
			return self.rightrotate(root)
		if balance < -1 and key > root.right.data:
			return self.leftrotate(root)
		if balance < -1 and key < root.right.data:
			root.right = self.rightrotate(root.right)
			return self.leftrotate(root)
		return root


class Solution:

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

	def getBalance(self, root):
		if root == None:
			return 0
		return self.getHeight(root.left) - self.getHeight(root.right)

	def leftRotate(self, root):
		y = root.right
		t2 = y.left
		root.right = t2
		y.left = root
		root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
		y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
		return y

	def rightRotate(self, root):
		y = root.left
		t2 = y.right
		root.left = t2
		y.right = root
		root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
		y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
		return y

	def insertToAVL(self, root, key):
		if not root:
			root = Node(key)
			return root
		elif key == root.data:
			return root
		elif key < root.data:
			root.left = self.insertToAVL(root.left, key)
		else:
			root.right = self.insertToAVL(root.right, key)
		root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
		b = self.getBalance(root)
		if b > 1 and key < root.left.data:
			return self.rightRotate(root)
		if b < -1 and key > root.right.data:
			return self.leftRotate(root)
		if b > 1 and key > root.left.data:
			root.left = self.leftRotate(root.left)
			return self.rightRotate(root)
		if b < -1 and key < root.right.data:
			root.right = self.rightRotate(root.right)
			return self.leftRotate(root)
		return root


class Solution:

	def insertToAVL(self, root, key):
		if root == None:
			return Node(key)
		if key < root.data:
			root.left = self.insertToAVL(root.left, key)
		elif key > root.data:
			root.right = self.insertToAVL(root.right, key)
		root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
		bal = self.getBalance(root)
		if bal > 1 and self.getBalance(root.left) >= 0:
			return self.rotateRight(root)
		elif bal > 1 and self.getBalance(root.left) < 0:
			root.left = self.rotateLeft(root.left)
			return self.rotateRight(root)
		elif bal < -1 and self.getBalance(root.right) <= 0:
			return self.rotateLeft(root)
		elif bal < -1 and self.getBalance(root.right) > 0:
			root.right = self.rotateRight(root.right)
			return self.rotateLeft(root)
		return root

	def getBalance(self, root):
		if root == None:
			return 0
		return self.getHeight(root.left) - self.getHeight(root.right)

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

	def rotateRight(self, root):
		(x, y, z) = (root, root.left, root.left.left)
		x.left = y.right
		y.right = x
		x.height = 1 + max(self.getHeight(x.left), self.getHeight(x.right))
		y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
		return y

	def rotateLeft(self, root):
		(x, y, z) = (root, root.right, root.right.right)
		x.right = y.left
		y.left = x
		x.height = 1 + max(self.getHeight(x.left), self.getHeight(x.right))
		y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
		return y


class Solution:

	def insertToAVL(self, node, key):
		if node == None:
			return Node(key)
		else:
			if key < node.data:
				node.left = self.insertToAVL(node.left, key)
			elif key > node.data:
				node.right = self.insertToAVL(node.right, key)
			else:
				return node
			lh = self.nodeHeight(node.left)
			rh = self.nodeHeight(node.right)
			if lh > rh:
				node.height = 1 + lh
			else:
				node.height = 1 + rh
			balance = self.nodeHeight(node.left) - self.nodeHeight(node.right)
			if balance > 1 and key < node.left.data:
				return self.rRight(node)
			if balance < -1 and key > node.right.data:
				return self.rLeft(node)
			if balance > 1 and key > node.left.data:
				node.left = self.rLeft(node.left)
				return self.rRight(node)
			if balance < -1 and key < node.right.data:
				node.right = self.rRight(node.right)
				return self.rLeft(node)
			return node

	def nodeHeight(self, node):
		if node == None:
			return 0
		else:
			return node.height

	def rLeft(self, rnode):
		RN = rnode.right
		LN = RN.left
		RN.left = rnode
		rnode.right = LN
		rnode.height = 1 + max(self.nodeHeight(rnode.left), self.nodeHeight(rnode.right))
		RN.height = 1 + max(self.nodeHeight(RN.left), self.nodeHeight(RN.right))
		return RN

	def rRight(self, rnode):
		LN = rnode.left
		RN = LN.right
		LN.right = rnode
		rnode.left = RN
		rnode.height = 1 + max(self.nodeHeight(rnode.left), self.nodeHeight(rnode.right))
		LN.height = 1 + max(self.nodeHeight(LN.left), self.nodeHeight(LN.right))
		return LN


class Solution:

	def height(self, h):
		if h == None:
			return 0
		return h.height

	def getBalance(self, h):
		if not h:
			return 0
		return self.height(h.left) - self.height(h.right)

	def rotateLeft(self, h):
		x = h.right
		h.right = x.left
		x.left = h
		h.height = max(self.height(h.left), self.height(h.right)) + 1
		x.height = max(self.height(x.left), self.height(x.right)) + 1
		return x

	def rotateRight(self, h):
		x = h.left
		h.left = x.right
		x.right = h
		h.height = max(self.height(h.left), self.height(h.right)) + 1
		x.height = max(self.height(x.left), self.height(x.right)) + 1
		return x

	def insertToAVL(self, root, key):
		if not root:
			return Node(key)
		if root.data < key:
			root.right = self.insertToAVL(root.right, key)
		elif root.data > key:
			root.left = self.insertToAVL(root.left, key)
		else:
			return root
		root.height = max(self.height(root.left), self.height(root.right)) + 1
		balance = self.getBalance(root)
		if balance > 1:
			if key > root.left.data:
				root.left = self.rotateLeft(root.left)
			return self.rotateRight(root)
		elif balance < -1:
			if key < root.right.data:
				root.right = self.rotateRight(root.right)
			return self.rotateLeft(root)
		return root