// 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
Following is the C implementation for AVL Tree Deletion.
// 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
Searching:
Algorithm to search for a key in a given Binary Search Tree:
#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