What is Data Structure?

A data structure is a storage that is used to store and organize data. It is a

way of arranging data on a computer so that it can be accessed and updated
efficiently.
A data structure is not only used for organizing the data. It is also used for
processing, retrieving, and storing data. There are different basic and
advanced types of data structures that are used in almost every program or
software system that has been developed.

Classification of Data Structure:

1. Linear Data Structure: Data structure in which data elements are

arranged sequentially or linearly, where each element is attached to its
previous and next adjacent elements, is called a linear data structure.
Example: Array, Stack, Queue, Linked List, etc.
2. Static Data Structure: Static data structure has a fixed memory size. It is
easier to access the elements in a static data structure.
Example: array.
3. Dynamic Data Structure: In dynamic data structure, the size is not fixed.
It can be randomly updated during the runtime which may be considered
efficient concerning the memory (space) complexity of the code.
Example: Queue, Stack, etc.
4. Non-Linear Data Structure: Data structures where data elements are not
placed sequentially or linearly are called non-linear data structures. In a
non-linear data structure, we can’t traverse all the elements in a single run
only.
Examples: Trees and Graphs.

Tree Data Structure

Tree Data Structure is a non-linear data structure in which a collection of
elements known as nodes are connected to each other via edges such that
there exists exactly one path between any two nodes.

The topmost node of the tree is called the root, and the nodes below it are
called the child nodes. Each node can have multiple child nodes, and these
child nodes can also have their own child nodes, forming a recursive
structure.

Terminologies In Tree Data Structure

 Parent Node: The node which is a predecessor of a node is called the
parent node of that node. {B} is the parent node of {D, E}.
 Child Node: The node which is the immediate successor of a node is
called the child node of that node. Examples: {D, E} are the child nodes
of {B}.
 Root Node: The topmost node of a tree or the node which does not have
any parent node is called the root node. {A} is the root node of the tree. A
non-empty tree must contain exactly one root node and exactly one path
from the root to all other nodes of the tree.
 Leaf Node or External Node: The nodes which do not have any child
nodes are called leaf nodes. {I, J, K, F, G, H} are the leaf nodes of the
tree.
 Ancestor of a Node: Any predecessor nodes on the path of the root to
that node are called Ancestors of that node. {A,B} are the ancestor nodes
of the node {E}
 Descendant: A node x is a descendant of another node y if and only if y
is an ancestor of x.
 Sibling: Children of the same parent node are called siblings. {D,E} are
called siblings.
 Level of a node: The count of edges on the path from the root node to
that node. The root node has level 0.
 Internal node: A node with at least one child is called Internal Node.
 Neighbor of a Node: Parent or child nodes of that node are called
neighbors of that node.
 Subtree: Any node of the tree along with its descendant.

Types of Tree Data Structure

 Binary tree: In a binary tree, each node can have a maximum of two
children linked to it. Some common types of binary trees include full
binary trees, complete binary trees, balanced binary trees, and
degenerate or pathological binary trees.
 Ternary Tree: A Ternary Tree is a tree data structure in which each node
has at most three child nodes, usually distinguished as “left”, “mid” and
“right”.
 N-ary Tree or Generic Tree: Generic trees are a collection of nodes
where each node is a data structure that consists of records and a list of
references to its children(duplicate references are not allowed). Unlike the
linked list, each node stores the address of multiple nodes.
Applications of Tree Data Structure
 File System: This allows for efficient navigation and organization of files.
 Data Compression: Huffman coding is a popular technique for data
compression that involves constructing a binary tree where the leaves
represent characters and their frequency of occurrence. The resulting tree
is used to encode the data in a way that minimizes the amount of storage
required.
 Compiler Design: In compiler design, a syntax tree is used to represent
the structure of a program.
 Database Indexing: B-trees and other tree structures are used in
database indexing to efficiently search for and retrieve data.

Basic Operations Of Tree Data Structure:

 Create – create a tree in the data structure.
 Insert − Inserts data in a tree.
 Search − Searches specific data in a tree to check whether it is present
or not.
 Traversal:
o Depth-First-Search Traversal
o Breadth-First-Search Traversal

Binary Tree is a non-linear data structure where each node has at most
two children.

Representation of Binary Tree

Each node in a Binary Tree has three parts:
 Data
 Pointer to the left child
 Pointer to the right child
Types of Binary Tree
Binary Tree can be classified into multiples types based on multiple factors:
 On the basis of Number of Children
o Full Binary Tree
o Degenerate Binary Tree
o Skewed Binary Trees
 On the basis of Completion of Levels
o Complete Binary Tree
o Perfect Binary Tree
o Balanced Binary Tree
 On the basis of Node Values:
o Binary Search Tree
o AVL Tree
o Red Black Tree
o B Tree
o B+ Tree
o Segment Tree

A full binary tree is a binary tree with either zero or two child nodes for each
node.

Every non-leaf node has just one child in a binary tree known as
a Degenerate Binary tree.

Degenerate Binary tree is of two types:

 Left-skewed Tree: If all the nodes in the degenerate tree have only a left
child.
 Right-skewed Tree: If all the nodes in the degenerate tree have only a
right child.
A skewed binary tree is a type of binary tree in which all the nodes have only
either one child or no child.
Types of Skewed Binary trees
There are 2 special types of skewed tree:

A complete binary tree is a special type of binary tree where all the levels of
the tree are filled completely except the lowest level nodes which are filled
from as left as possible.

A perfect binary tree is a special type of binary tree in which all the leaf
nodes are at the same depth, and all non-leaf nodes have two children. In
simple terms, this means that all leaf nodes are at the maximum depth of the
tree, and the tree is completely filled with no gaps.

A balanced binary tree is a binary tree that follows the 3 conditions:

 The height of the left and right tree for any node does not differ by more
than 1.
 The left subtree of that node is also balanced.
 The right subtree of that node is also balanced.

A Binary Search Tree is a data structure used in computer science for

organizing and storing data in a sorted manner. Each node in a Binary
Search Tree has at most two children, a left child and a right child, with
the left child containing values less than the parent node and the right child
containing values greater than the parent node. This hierarchical structure
allows for efficient searching, insertion, and deletion operations on the
data stored in the tree.
Given a Binary Search Tree, The task is to print the elements in inorder,
preorder, and postorder traversal of the Binary Search Tree.
Input:

A Binary Search Tree

Output:
Inorder Traversal: 10 20 30 100 150 200 300
Preorder Traversal: 100 20 10 30 200 150 300
Postorder Traversal: 10 30 20 150 300 200 100
Input:

Binary Search Tree

Output:
Inorder Traversal: 8 12 20 22 25 30 40
Preorder Traversal: 22 12 8 20 30 25 40
Postorder Traversal: 8 20 12 25 40 30 22
AVL Tree:
An AVL tree defined as a self-balancing Binary Search Tree (BST) where
the difference between heights of left and right subtrees for any node cannot
be more than one.

The difference between the heights of the left subtree and the right subtree
for any node is known as the balance factor of the node.

The AVL tree is named after its inventors, Georgy Adelson-Velsky and
Evgenii Landis, who published it in their 1962 paper “An algorithm for the
organization of information”.

Example of AVL Tree:

The above tree is AVL because the differences between the heights of left
and right subtrees for every node are less than or equal to 1.
Example of a Tree that is NOT an AVL Tree:

The above tree is not AVL because the differences between the heights of
the left and right subtrees for 8 and 12 are greater than 1.

Why AVL Trees?

Most of the BST operations (e.g., search, max, min, insert, delete.. etc)
take O(h) time where h is the height of the BST. The cost of these
operations may become O(n) for a skewed Binary tree. If we make sure
that the height of the tree remains O(log(n)) after every insertion and
deletion, then we can guarantee an upper bound of O(log(n)) for all these
operations. The height of an AVL tree is always O(log(n)) where n is the
number of nodes in the tree.

Operations on an AVL Tree:

 Insertion
 Deletion
 Searching

Rotating the subtrees in an AVL Tree:

An AVL tree may rotate in one of the following four ways to keep itself
balanced:
Left Rotation:
When a node is added into the right subtree of the right subtree, if the tree
gets out of balance, we do a single left rotation.
Right Rotation:
If a node is added to the left subtree of the left subtree, the AVL tree may get
out of balance, we do a single right rotation.

Left-Right Rotation:
A left-right rotation is a combination in which first left rotation takes place
after that right rotation executes.
Right-Left Rotation:
A right-left rotation is a combination in which first right rotation takes place
after that left rotation executes.

Applications of AVL Tree:

1. It is used to index huge records in a database and also to efficiently
search in that.
2. For all types of in-memory collections, including sets and dictionaries,
AVL Trees are used.
3. Database applications, where insertions and deletions are less common
but frequent data lookups are necessary
4. Software that needs optimized search.

Advantages of AVL Tree:

1. AVL trees can self-balance themselves.
2. It is surely not skewed.
3. It provides faster lookups than Red-Black Trees
4. Better searching time complexity compared to other trees like binary tree.
5. Height cannot exceed log(N), where, N is the total number of nodes in the
tree

Disadvantages of AVL Tree:

1. It is difficult to implement.
2. It has high constant factors for some of the operations.
3. Less used compared to Red-Black trees.
4. Due to its rather strict balance, AVL trees provide complicated insertion
and removal operations as more rotations are performed.
5. Take more processing for balancing.

Insertion in AVL Tree:

To make sure that the given tree remains AVL after every insertion, we must
augment the standard BST insert operation to perform some re-balancing.
Following are two basic operations that can be performed to balance a BST
without violating the BST property (keys(left) < key(root) < keys(right)).
 Left Rotation
 Right Rotation

T1, T2 and T3 are subtrees of the tree, rooted with y (on the left
side) or x (on the right side)

y x
/ \ Right Rotation / \
x T3 - - - - - - - > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3

Keys in both of the above trees follow the following order

keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.
Steps to follow for insertion:
Let the newly inserted node be w
 Perform standard BST insert for w.
 Starting from w, travel up and find the first unbalanced node. Let z be
the first unbalanced node, y be the child of z that comes on the path
from w to z and x be the grandchild of z that comes on the path
from w to z.
 Re-balance the tree by performing appropriate rotations on the subtree
rooted with z. There can be 4 possible cases that need to be handled
as x, y and z can be arranged in 4 ways.
 Following are the possible 4 arrangements:
o y is the left child of z and x is the left child of y (Left Left Case)
o y is the left child of z and x is the right child of y (Left Right
Case)
o y is the right child of z and x is the right child of y (Right Right
Case)
o y is the right child of z and x is the left child of y (Right Left Case)

Following are the operations to be performed in above mentioned 4 cases. In

all of the cases, we only need to re-balance the subtree rooted with z and
the complete tree becomes balanced as the height of the subtree (After
appropriate rotations) rooted with z becomes the same as it was before
insertion.

1. Left Left Case

T1, T2, T3 and T4 are subtrees.
z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
2. Left Right Case

3. Right Right Case

z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4

4. Right Left Case

z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
Illustration of Insertion at AVL Tree
Approach:
The idea is to use recursive BST insert, after insertion, we get pointers to all
ancestors one by one in a bottom-up manner. So we don‟t need a parent
pointer to travel up. The recursive code itself travels up and visits all the
ancestors of the newly inserted node.

Follow the steps mentioned below to implement the idea:

 Perform the normal BST insertion.
 The current node must be one of the ancestors of the newly inserted
node. Update the height of the current node.
 Get the balance factor (left subtree height – right subtree height) of the
current node.
 If the balance factor is greater than 1, then the current node is
unbalanced and we are either in the Left Left case or left Right case. To
 check whether it is left left case or not, compare the newly inserted key
with the key in the left subtree root.
 If the balance factor is less than -1, then the current node is unbalanced
and we are either in the Right Right case or Right-Left case. To check
whether it is the Right Right case or not, compare the newly inserted key
with the key in the right subtree root.

// C program to insert a node in AVL tree

#include<stdio.h>
#include<stdlib.h>

// An AVL tree node

struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};

// A utility function to get the height of the tree

int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}

// A utility function to get maximum of two integers

int max(int a, int b)
{
return (a > b)? a : b;
}

/* Helper function that allocates a new node with the given key and
NULL left and right pointers. */
struct Node* newNode(int key)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}

// A utility function to right rotate subtree rooted with y

// See the diagram given above.
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
 struct Node *T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(height(y->left),
height(y->right)) + 1;
x->height = max(height(x->left),
height(x->right)) + 1;

// Return new root

return x;
}

// A utility function to left rotate subtree rooted with x

// See the diagram given above.
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;

// Return new root

return y;
}

// Get Balance factor of node N

int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}

// Recursive function to insert a key in the subtree rooted

// with node and returns the new root of the subtree.
struct Node* insert(struct Node* node, int key)
{
/* 1. Perform the normal BST insertion */
if (node == NULL)
return(newNode(key));

if (key < node->key)

 node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys are not allowed in BST
return node;

/* 2. Update height of this ancestor node */

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

/* 3. Get the balance factor of this ancestor

node to check whether this node became
unbalanced */
int balance = getBalance(node);

// If this node becomes unbalanced, then

// there are 4 cases

// Left Left Case

if (balance > 1 && key < node->left->key)
return rightRotate(node);

// Right Right Case

if (balance < -1 && key > node->right->key)
return leftRotate(node);

// Left Right Case

if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}

// Right Left Case

if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}

/* return the (unchanged) node pointer */

return node;
}

// A utility function to print preorder traversal

// of the tree.
// The function also prints height of every node
void preOrder(struct Node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}

/* Driver program to test above function*/

int main()
{
struct Node *root = NULL;

/* Constructing tree given in the above figure */

root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);

/* The constructed AVL Tree would be

30
/ \
20 40
/ \ \
10 25 50
*/

printf("Preorder traversal of the constructed AVL"

" tree is \n");
preOrder(root);

return 0;
}

Output
Preorder traversal of the constructed AVL tree is
30 20 10 25 40 50

Complexity Analysis
Time Complexity: O(log(n)), For Insertion
Auxiliary Space: O(1)
The rotation operations (left and right rotate) take constant time as only a
few pointers are being changed there. Updating the height and getting the
balance factor also takes constant time. So the time complexity of the AVL
insert remains the same as the BST insert which is O(h) where h is the
height of the tree. Since the AVL tree is balanced, the height is O(Logn). So
time complexity of AVL insert is O(Logn).
Steps to follow for deletion.
To make sure that the given tree remains AVL after every deletion, we must
augment the standard BST delete operation to perform some re-balancing.
Following are two basic operations that can be performed to re-balance a
BST without violating the BST property (keys(left) < key(root) < keys(right)).
1. Left Rotation
2. Right Rotation

T1, T2 and T3 are subtrees of the tree rooted with y (on left side)
or x (on right side)
y x
/ \ Right Rotation / \
x T3 – - – - – - – > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
Keys in both of the above trees follow the following order
keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.

Let w be the node to be deleted

1. Perform standard BST delete for w.
2. Starting from w, travel up and find the first unbalanced node. Let z be the
first unbalanced node, y be the larger height child of z, and x be the larger
height child of y. Note that the definitions of x and y are different
from insertion here.
3. Re-balance the tree by performing appropriate rotations on the subtree
rooted with z. There can be 4 possible cases that needs to be handled as
x, y and z can be arranged in 4 ways. Following are the possible 4
arrangements:
1. y is left child of z and x is left child of y (Left Left Case)
2. y is left child of z and x is right child of y (Left Right Case)
3. y is right child of z and x is right child of y (Right Right Case)
4. y is right child of z and x is left child of y (Right Left Case)
Like insertion, following are the operations to be performed in above
mentioned 4 cases. Note that, unlike insertion, fixing the node z won’t fix the
complete AVL tree. After fixing z, we may have to fix ancestors of z as well
a) Left Left Case

T1, T2, T3 and T4 are subtrees.

z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2

b) Left Right Case

z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2

c) Right Right Case

z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
d) Right Left Case

z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4

Unlike insertion, in deletion, after we perform a rotation at z, we may have to

perform a rotation at ancestors of z. Thus, we must continue to trace the
path until we reach the root.
Example:
A node with value 32 is being deleted. After deleting 32, we travel up and
find the first unbalanced node which is 44. We mark it as z, its higher height
child as y which is 62, and y’s higher height child as x which could be either
78 or 50 as both are of same height. We have considered 78. Now the case
is Right Right, so we perform left rotation.
C implementation
Following is the C implementation for AVL Tree Deletion. The following C
implementation uses the recursive BST delete as basis. In the recursive BST
delete, after deletion, we get pointers to all ancestors one by one in bottom
up manner. So we don’t need parent pointer to travel up. The recursive code
itself travels up and visits all the ancestors of the deleted node.
1. Perform the normal BST deletion.
2. The current node must be one of the ancestors of the deleted node.
Update the height of the current node.
3. Get the balance factor (left subtree height – right subtree height) of the
current node.
4. If balance factor is greater than 1, then the current node is unbalanced
and we are either in Left Left case or Left Right case. To check whether it
is Left Left case or Left Right case, get the balance factor of left subtree.
If balance factor of the left subtree is greater than or equal to 0, then it is
Left Left case, else Left Right case.
5. If balance factor is less than -1, then the current node is unbalanced and
we are either in Right Right case or Right Left case. To check whether it
is Right Right case or Right Left case, get the balance factor of right
subtree. If the balance factor of the right subtree is smaller than or equal
to 0, then it is Right Right case, else Right Left case.

// C program to delete a node from AVL Tree

#include<stdio.h>
#include<stdlib.h>

// An AVL tree node

struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};

// A utility function to get maximum of two integers

int max(int a, int b);

// A utility function to get height of the tree

int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}

// A utility function to get maximum of two integers

int max(int a, int b)
{
return (a > b)? a : b;
}

/* Helper function that allocates a new node with the given key and
NULL left and right pointers. */
struct Node* newNode(int key)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}

// A utility function to right rotate subtree rooted with y

// See the diagram given above.
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;

// Return new root

return x;
}

// A utility function to left rotate subtree rooted with x

// See the diagram given above.
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;

// Return new root

return y;
}

// Get Balance factor of node N

int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}

struct Node* insert(struct Node* node, int key)

{
/* 1. Perform the normal BST rotation */
if (node == NULL)
return(newNode(key));

if (key < node->key)

node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys not allowed
 return node;

/* 2. Update height of this ancestor node */

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

/* 3. Get the balance factor of this ancestor

node to check whether this node became
unbalanced */
int balance = getBalance(node);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case

if (balance > 1 && key < node->left->key)
return rightRotate(node);

// Right Right Case

if (balance < -1 && key > node->right->key)
return leftRotate(node);

// Left Right Case

if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}

// Right Left Case

if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}

/* return the (unchanged) node pointer */

return node;
}

/* Given a non-empty binary search tree, return the

node with minimum key value found in that tree.
Note that the entire tree does not need to be
searched. */
struct Node * minValueNode(struct Node* node)
{
struct Node* current = node;

/* loop down to find the leftmost leaf */

while (current->left != NULL)
current = current->left;

return current;
}
// Recursive function to delete a node with given key
// from subtree with given root. It returns root of
// the modified subtree.
struct Node* deleteNode(struct Node* root, int key)
{
// STEP 1: PERFORM STANDARD BST DELETE

if (root == NULL)
return root;

// If the key to be deleted is smaller than the

// root's key, then it lies in left subtree
if ( key < root->key )
root->left = deleteNode(root->left, key);

// If the key to be deleted is greater than the

// root's key, then it lies in right subtree
else if( key > root->key )
root->right = deleteNode(root->right, key);

// if key is same as root's key, then This is

// the node to be deleted
else
{
// node with only one child or no child
if( (root->left == NULL) || (root->right == NULL) )
{
struct Node *temp = root->left ? root->left :
root->right;

// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child
free(temp);
}
else
{
// node with two children: Get the inorder
// successor (smallest in the right subtree)
struct Node* temp = minValueNode(root->right);

// Copy the inorder successor's data to this node

root->key = temp->key;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->key);
}
}
 // If the tree had only one node then return
if (root == NULL)
return root;

// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE

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

// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to

// check whether this node became unbalanced)
int balance = getBalance(root);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case

if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);

// Left Right Case

if (balance > 1 && getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}

// Right Right Case

if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);

// Right Left Case

if (balance < -1 && getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}

// A utility function to print preorder traversal of

// the tree.
// The function also prints height of every node
void preOrder(struct Node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}

/* Driver program to test above function*/

int main()
{
struct Node *root = NULL;

/* Constructing tree given in the above figure */

root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);

/* The constructed AVL Tree would be

9
/ \
1 10
/ \ \
0 5 11
/ / \
-1 2 6
*/

printf("Preorder traversal of the constructed AVL "

"tree is \n");
preOrder(root);

root = deleteNode(root, 10);

/* The AVL Tree after deletion of 10

1
/ \
0 9
/ / \
-1 5 11
/ \
2 6
*/

printf("\nPreorder traversal after deletion of 10 \n");

preOrder(root);

return 0;
}

Output:
Preorder traversal of the constructed AVL tree is
9 1 0 -1 5 2 6 10 11
Preorder traversal after deletion of 10
1 0 -1 9 5 2 6 11
Time Complexity: The rotation operations (left and right rotate) take
constant time as only few pointers are being changed there. Updating the
height and getting the balance factor also take constant time. So the time
complexity of AVL delete remains same as BST delete which is O(h) where h
is height of the tree. Since AVL tree is balanced, the height is O(Logn). So
time complexity of AVL delete is O(Log n).
Auxiliary Space: O(1), since no extra space is used.
Advantages Of AVL Trees
 It is always height balanced
 Height Never Goes Beyond LogN, where N is the number of nodes
 It give better search than compared to binary search tree
 It has self balancing capabilities
Summary of AVL Trees
 These are self-balancing binary search trees.
 Balancing Factor ranges -1, 0, and +1.
 When balancing factor goes beyond the range require rotations to be
performed
 Insert, delete, and search time is O(log N).
 AVL tree are mostly used where search is more frequent compared to
insert and delete operation.

Searching:

Algorithm to search for a key in a given Binary Search Tree:

Let’s say we want to search for the number X, We start at the root. Then:
 We compare the value to be searched with the value of the root.
o If it’s equal we are done with the search if it’s smaller we know
that we need to go to the left subtree because in a binary search
tree all the elements in the left subtree are smaller and all the
elements in the right subtree are larger.
 Repeat the above step till no more traversal is possible
 If at any iteration, key is found, return True. Else False.

#include <stdio.h>
#include <stdlib.h>

struct Node {
int key;
struct Node* left;
struct Node* right;
};

// Constructor to create a new BST node

struct Node* newNode(int item)
{
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// function to search a key in a BST

struct Node* search(struct Node* root, int key)
{

// Base Cases: root is null or key is

// present at root
if (root == NULL || root->key == key)
return root;

// Key is greater than root's key

if (root->key < key)
return search(root->right, key);

// Key is smaller than root's key

return search(root->left, key);
}

// Driver Code
int main()
{
// Creating a hard coded tree for keeping
// the length of the code small. We need
// to make sure that BST properties are
// maintained if we try some other cases.
struct Node* root = newNode(50);
root->left = newNode(30);
root->right = newNode(70);
root->left->left = newNode(20);
root->left->right = newNode(40);
root->right->left = newNode(60);
root->right->right = newNode(80);

printf(search(root, 19) != NULL ? "Found\n"

: "Not Found\n");
printf(search(root, 80) != NULL ? "Found\n"
: "Not Found\n");
 return 0;
}

Output
Not Found
Found

Iterative searching in Binary Search Tree

#include <stdio.h>
#include <stdlib.h>

struct Node {
int key;
struct Node* left;
struct Node* right;
};

// Function to search a key in a BST

struct Node* search(struct Node* root, int key) {

// Traverse until root reaches a dead end

while (root != NULL) {

if (key > root->key) {

root = root->right;
} else if (key < root->key) {
root = root->left;
} else {
return root; // Key found
}
}
return NULL; // Key not present
}

// Function to create a new node

struct Node* newNode(int item) {
struct Node* temp =
(struct Node*)malloc(sizeof(struct Node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// Driver Code
int main() {

// Creating a hardcoded tree for keeping

// the length of the code small. We need
// to make sure that BST properties are
// maintained if we try some other cases.
struct Node* root = newNode(50);
root->left = newNode(30);
root->right = newNode(70);
root->left->left = newNode(20);
root->left->right = newNode(40);
root->right->left = newNode(60);
root->right->right = newNode(80);

search(root, 19) != NULL ? printf("Found\n") :

printf("Not Found\n");
search(root, 80) != NULL ? printf("Found\n") :
printf("Not Found\n");

return 0;
}

Output
Not Found
Found

Construct BST from given preorder traversal

Given the preorder traversal of a binary search tree, construct the BST.
Examples:
Input: {10, 5, 1, 7, 40, 50}
Output: 10
/ \
5 40
/ \ \
1 7 50
Naive approach: To solve the problem follow the below idea:
The first element of preorder traversal is always the root. We first construct
the root. Then we find the index of the first element which is greater than the
root. Let the index be „i‟. The values between root and „i‟ will be part of the
left subtree, and the values between „i'(inclusive) and „n-1‟ will be part of the
right subtree. Divide the given pre[] at index “i” and recur for left and right
sub-trees.
For example in {10, 5, 1, 7, 40, 50}, 10 is the first element, so we make it
root. Now we look for the first element greater than 10, we find 40. So we
know the structure of BST is as follows.:
10
/ \
{5, 1, 7} {40, 50}
We recursively follow the above steps for subarrays {5, 1, 7} and {40, 50},
and get the complete tree.

// C program for the above approach

#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child

and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};

// A utility function to create a node

struct node* newNode(int data)
{
struct node* temp
= (struct node*)malloc(sizeof(struct node));

temp->data = data;
temp->left = temp->right = NULL;

return temp;
}

// A recursive function to construct Full from pre[].

// preIndex is used to keep track of index in pre[].
struct node* constructTreeUtil(int pre[], int* preIndex,
int low, int high, int size)
{
// Base case
if (*preIndex >= size || low > high)
return NULL;

// The first node in preorder traversal is root. So take

 // the node at preIndex from pre[] and make it root, and
// increment preIndex
struct node* root = newNode(pre[*preIndex]);
*preIndex = *preIndex + 1;

// If the current subarray has only one element, no need

// to recur
if (low == high)
return root;

// Search for the first element greater than root

int i;
for (i = low; i <= high; ++i)
if (pre[i] > root->data)
break;

// Use the index of element found in preorder to divide

// preorder array in two parts. Left subtree and right
// subtree
root->left = constructTreeUtil(pre, preIndex, *preIndex,
i - 1, size);
root->right
= constructTreeUtil(pre, preIndex, i, high, size);

return root;
}

// The main function to construct BST from given preorder

// traversal. This function mainly uses constructTreeUtil()
struct node* constructTree(int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil(pre, &preIndex, 0, size - 1,
size);
}

// A utility function to print inorder traversal of a Binary

// Tree
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}

// Driver code
int main()
{
int pre[] = { 10, 5, 1, 7, 40, 50 };
int size = sizeof(pre) / sizeof(pre[0]);

// Function call
struct node* root = constructTree(pre, size);
 printInorder(root);

return 0;
}

Output
Inorder traversal of the constructed tree:
1 5 7 10 40 50