# Avl tree node insertion in swift

``````import Foundation
// Swift 4 program
// AVL Tree insertion

// Avl Tree Node
class TreeNode
{
var data: Int;
var height: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value of avl tree
self.data = data;
self.height = 1;
self.left = nil;
self.right = nil;
}
}
class AvlTree
{
// Tree root node
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Get the height of given node
func getHeight(_ node: TreeNode? ) -> Int
{
if (node == nil)
{
return 0;
}
return node!.height;
}
// Get the max value of given two numbers
func maxHeight(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Perform the Right rotate operation
func rightRotate(_ node: TreeNode? ) -> TreeNode?
{
// Get left child node
let leftNode: TreeNode? = node!.left;
// Get left node right subtree
let rightSubtree: TreeNode? = 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
func leftRotate(_ node: TreeNode? ) -> TreeNode?
{
// Get right child node
let rightNode: TreeNode? = node!.right;
// Get right node left subtree
let leftSubtree: TreeNode? = 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
func getBalanceFactor(_ node: TreeNode? ) -> Int
{
if (node == nil)
{
return 0;
}
return self.getHeight(node!.left) -
self.getHeight(node!.right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (data) are not allowed
func addNode(_ node: TreeNode? , _ data : Int) -> TreeNode?
{
if (node == nil)
{
// Return a new node
return TreeNode(data);
}
if (data < node!.data)
{
}
else if (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
let factor: Int = self.getBalanceFactor(node);
// LL Case
if (factor > 1 && data < node!.left!.data)
{
return self.rightRotate(node);
}
// RR Case
if (factor < -1 && data > node!.right!.data)
{
return self.leftRotate(node);
}
// LL Case
if (factor > 1 && data > node!.left!.data)
{
node!.left = self.leftRotate(node!.left);
return self.rightRotate(node);
}
// RR Case
if (factor < -1 && data < node!.right!.data)
{
node!.right = self.rightRotate(node!.right);
return self.leftRotate(node);
}
return node;
}
// Print the tree in preorder form
func preorder(_ node: TreeNode? )
{
if (node  != nil)
{
print("  "
+ String(node!.data), terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
// Print the tree in inorder form
func inorder(_ node: TreeNode? )
{
if (node  != nil)
{
self.inorder(node!.left);
print("",node!.data, terminator: " ");
self.inorder(node!.right);
}
}
// Print the tree in postorder form
func postorder(_ node: TreeNode? )
{
if (node  != nil)
{
self.postorder(node!.left);
self.postorder(node!.right);
print("",node!.data, terminator: " ");
}
}
static func main(_ args: [String])
{
let tree: AvlTree? = AvlTree();
/*
Resultant  AVL Tree
-----------------
7
/  \
/    \
4      17
/ \     / \
2   5  13  19
/ \     /
-3   3   11
*/
print("Resultant AVL Tree");
print("Preorder  :", terminator: "");
tree!.preorder(tree!.root);
print("\nInorder   :", terminator: "");
tree!.inorder(tree!.root);
print("\nPostorder :", terminator: "");
tree!.postorder(tree!.root);
}
}
AvlTree.main([String]());``````

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.