# Avl tree node insertion in python

Python program for Avl tree node insertion. Here problem description and explanation.

``````#  Python 3 program
#  AVL Tree insertion

#  Avl Tree Node
class TreeNode :
def __init__(self, data) :
#  Set node value of avl tree
self.data = data
self.height = 1
self.left = None
self.right = None

class AvlTree :
#  Tree root node
def __init__(self) :
self.root = None

#  Get the height of given node
def getHeight(self, node) :
if (node == None) :
return 0

return node.height

#  Get the max value of given two numbers
def maxHeight(self, a, b) :
if (a > b) :
return a
else :
return b

#  Perform the Right rotate operation
def rightRotate(self, node) :
#  Get left child node
leftNode = node.left
#  Get left node right subtree
rightSubtree = leftNode.right
#  Update the left and right subtree
leftNode.right = node
node.left = rightSubtree
#  Change the height of modified node
node.height = self.maxHeight(
self.getHeight(node.left),
self.getHeight(node.right)) + 1
leftNode.height = self.maxHeight(
self.getHeight(leftNode.left),
self.getHeight(leftNode.right)) + 1
return leftNode

#  Perform the Left Rotate operation
def leftRotate(self, node) :
#  Get right child node
rightNode = node.right
#  Get right node left subtree
leftSubtree = rightNode.left
#  Update the left and right subtree
rightNode.left = node
node.right = leftSubtree
#  Change the height of modified node
node.height = self.maxHeight(
self.getHeight(node.left),
self.getHeight(node.right)) + 1
rightNode.height = self.maxHeight(
self.getHeight(rightNode.left),
self.getHeight(rightNode.right)) + 1
return rightNode

#  Get the balance factor
def getBalanceFactor(self, node) :
if (node == None) :
return 0

return self.getHeight(node.left) - self.getHeight(node.right)

#  Recursively, add a node in AVL tree
#  Duplicate keys (data) are not allowed
if (node == None) :
#  Return a new node
return TreeNode(data)

if (data < node.data) :
elif (data > node.data) :
else :
#  When given key data already exists
return node

#  Change the height of current node
node.height = 1 + self.maxHeight(
self.getHeight(node.left),
self.getHeight(node.right))
#  Get balance factor of a node
factor = self.getBalanceFactor(node)
#  LL Case
if (factor > 1 and data < node.left.data) :
return self.rightRotate(node)

#  RR Case
if (factor < -1 and data > node.right.data) :
return self.leftRotate(node)

#  LL Case
if (factor > 1 and data > node.left.data) :
node.left = self.leftRotate(node.left)
return self.rightRotate(node)

#  RR Case
if (factor < -1 and data < node.right.data) :
node.right = self.rightRotate(node.right)
return self.leftRotate(node)

return node

#  Print the tree in preorder form
def preorder(self, node) :
if (node != None) :
print("  ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)

#  Print the tree in inorder form
def inorder(self, node) :
if (node != None) :
self.inorder(node.left)
print("  ", node.data, end = "")
self.inorder(node.right)

#  Print the tree in postorder form
def postorder(self, node) :
if (node != None) :
self.postorder(node.left)
self.postorder(node.right)
print("  ", node.data, end = "")

def main() :
tree = AvlTree()
#  Resultant  AVL Tree
#  -----------------
#         7
#        /  \
#       /    \
#      4      17
#     / \     / \
#    2   5  13  19
#   / \     /
# -3   3   11
print("Resultant AVL Tree")
print("Preorder  :", end = "")
tree.preorder(tree.root)
print("\nInorder   :", end = "")
tree.inorder(tree.root)
print("\nPostorder :", end = "")
tree.postorder(tree.root)

if __name__ == "__main__": main()``````

Output

``````Resultant AVL Tree
Preorder  :   7   4   2   -3   3   5   17   13   11   19
Inorder   :   -3   2   3   4   5   7   11   13   17   19
Postorder :   -3   3   2   5   4   11   13   19   17   7``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.