# Avl tree node insertion in php

Php program for Avl tree node insertion. Here problem description and other solutions.

``````<?php
// Php program
// AVL Tree insertion

// Avl Tree Node
class TreeNode
{
public \$data;
public \$height;
public \$left;
public \$right;
public	function __construct(\$data)
{
// Set node value of avl tree
\$this->data = \$data;
\$this->height = 1;
\$this->left = NULL;
\$this->right = NULL;
}
}
class AvlTree
{
// Tree root node
public \$root;
public	function __construct()
{
\$this->root = NULL;
}
// Get the height of given node
public	function getHeight(\$node)
{
if (\$node == NULL)
{
return 0;
}
return \$node->height;
}
// Get the max value of given two numbers
public	function maxHeight(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
else
{
return \$b;
}
}
// Perform the Right rotate operation
public	function rightRotate(\$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 = \$this->maxHeight(
\$this->getHeight(\$node->left),
\$this->getHeight(\$node->right)) + 1;
\$leftNode->height = \$this->maxHeight(
\$this->getHeight(\$leftNode->left),
\$this->getHeight(\$leftNode->right)) + 1;
return \$leftNode;
}
// Perform the Left Rotate operation
public	function leftRotate(\$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 = \$this->maxHeight(
\$this->getHeight(\$node->left),
\$this->getHeight(\$node->right)) + 1;
\$rightNode->height = \$this->maxHeight(
\$this->getHeight(\$rightNode->left),
\$this->getHeight(\$rightNode->right)) + 1;
return \$rightNode;
}
// Get the balance factor
public	function getBalanceFactor(\$node)
{
if (\$node == NULL)
{
return 0;
}
return \$this->getHeight(\$node->left) -
\$this->getHeight(\$node->right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (data) are not allowed
{
if (\$node == NULL)
{
// Return a new node
return new 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 + \$this->maxHeight(
\$this->getHeight(\$node->left),
\$this->getHeight(\$node->right));
// Get balance factor of a node
\$factor = \$this->getBalanceFactor(\$node);
// LL Case
if (\$factor > 1 && \$data < \$node->left->data)
{
return \$this->rightRotate(\$node);
}
// RR Case
if (\$factor < -1 && \$data > \$node->right->data)
{
return \$this->leftRotate(\$node);
}
// LL Case
if (\$factor > 1 && \$data > \$node->left->data)
{
\$node->left = \$this->leftRotate(\$node->left);
return \$this->rightRotate(\$node);
}
// RR Case
if (\$factor < -1 && \$data < \$node->right->data)
{
\$node->right = \$this->rightRotate(\$node->right);
return \$this->leftRotate(\$node);
}
return \$node;
}
// Print the tree in preorder form
public	function preorder(\$node)
{
if (\$node != NULL)
{
printf("%d  ",\$node->data);
\$this->preorder(\$node->left);
\$this->preorder(\$node->right);
}
}
// Print the tree in inorder form
public	function inorder(\$node)
{
if (\$node != NULL)
{
\$this->inorder(\$node->left);
printf("%d  ",\$node->data);
\$this->inorder(\$node->right);
}
}
// Print the tree in postorder form
public	function postorder(\$node)
{
if (\$node != NULL)
{
\$this->postorder(\$node->left);
\$this->postorder(\$node->right);
printf("%d  ",\$node->data);
}
}
public static
function main(\$args)
{
\$tree = new AvlTree();
/*
Resultant  AVL Tree
-----------------
7
/  \
/    \
4      17
/ \     / \
2   5  13  19
/ \     /
-3   3   11
*/
printf("Resultant AVL Tree");
printf("\nPreorder  : ");
\$tree->preorder(\$tree->root);
printf("\nInorder   : ");
\$tree->inorder(\$tree->root);
printf("\nPostorder : ");
\$tree->postorder(\$tree->root);
}
}

AvlTree::main(array());``````

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.