Binary Search Trees and AVL trees Study Notes for GATE & Computer Science Engineering Exam

By Mukesh Kumar|Updated : March 22nd, 2021

A binary tree T, is termed binary search tree (or binary sorted tree), if every node N of T has the subsequent property. The worth at N is larger than each worth within the left subtree of N and is a smaller amount than or capable each value within the right subtree of N.

Here we are providing the complete study notes on the Binary Search Trees for the preparation of GATE, Computer Science Engineering Exam.

A BST holds the subsequent properties:

  • Each node can at most two child nodes.
  • The left subtree of a node have nodes with lesser key value than root node. 
  • The right subtree of a node have nodes with greater key value than root node
  • The subsequent left and right subtree must be binary search tree.
  • There always exist a unique path from the root node to every other node.

Traversals of Binary Search Tree

Inorder Tree Walk:

During inorder tree walk, first of all we visit the left node of the subtree then root of a subtree then right subtree visit.

Inorder traversal - Left- Node- Right

Inorder (x):

If xNIL {
   Inorder (left[x]);
   print key[x];
   Inorder (right[x]);}

Preorder Tree Walk:

In this type of tree traversals first of all we visit the root node then left subtree  then right subtree. 

Preorder - Node Left Right

Preorder (x) :

If x  NIL {
   print key[x];
   Preorder (left[x]);
   Preorder (right[x]);}

Postorder Tree Walk:

In this type of tree traversals first of all we visit the left subtree then right subtree and finally root node.

 Postorder - Left Right Node

Postorder(x):

If x NIL {
   Postorder (left[x]);
   Postorder (right[x]);
   print key [x];}

Search an element in BST:

Searching is a most basic operation which can be implemented as recursive or iterative function. Searching will be started from any node, if the node is null (tree is empty), then searching will result NULL which means that key isn't present in the tree. 

Otherwise, if the value of any node matches with that key, then the search is successful and result  the node. If the key value is less than that of node value, so we will search in left-subtree of the tree, and if key value is greater than node value, then we will search in right subtree. 

Same process will be repeated for subsequent trees as well. To search any key in the tree we need to start searching from root node. 

Insertion of an element:

Insertion can be done easily with the help of searching, because for inserting element at suitable position, we need to identify the perfect place of that element. In insertion we check the root node and insert new node into left subtree if its key value is less than root, otherwise we will insert it into right subtree, and this process is done recursively. 

If the new key already present in the tree, so we will never create duplicate nodes, we will either replace the old value with new onw, or don't do anything.

Deletion of an element:-

The deletion of an element from the tree is a little bit complex task. To delete a node, we want to search that node with the key, and then remove it from the tree. There are three cases to consider:

  • Deleting a leaf: for deleting a node present at leaf we can simply remove it from the tree without any further action.
  • Deleting a node with one child node: To delete a node with one child node remove the node and replace it with its child.
  • Deleting a node with two child node: first find its in-order successor (left-most node in its right sub-tree), let's say R. After finding R, copy R's key and value to the node, and then remove R from its right sub-tree.

Key Points of BST

  • It will take θ (n) time to traverse (inorder, preorder and postorder) n nodes of a tree.
  • A BST with height h, Search, Minimum, Maximum, Successor, Predecessor, Insert, and Delete operations can run in O(h) time.
  • The height of the BST is equal to the number of links from the root node to the deepest node.

The cons in a BST is that if every item which is to be inserted is greater than the previous item, then it will become a right skewed BST or if its every inserted item is less than to the previous item, then it will become a left skewed BST.


To avoid the skewed problem of BST, concept of AVL- tree or height balanced tree introduced

Balanced Binary Trees: Balancing a binary tree ensures that the interior path lengths are nearly close to O(nlogn). B trees and AVL trees are balanced binary trees.

 Example 1: Number of leaves in the binary search tree

int numberofleaves(struct bstnode * node){    int total = 0;    if(node->Left == 0 && node->Right == 0)        return 1;             if(node->Left!= 0)                                total += numberofleaves(node->Left);      if(node->Right!=0)                                total += numberofleaves(node->Right);     return total;          }

Example  2: Find the Diameter (Diameter of a tree is the longest path between two leaf nodes in a tree) of a binary tree

int diameter(struct btnode *root, int *height){ int leftH = 0, rightH = 0; int leftD = 0, rightD = 0;  if(root == NULL) { *height = 0; return 0; } leftD = diameter(root->left, &leftH); rightD = diameter(root->right, &rightH); *height = max(leftH, rightH) + 1;
return max(leftH + rightH + 1, max(leftD, rightD));}

Example 3: Apply search operation in the Binary tree using iteration

struct bstnode *search(int value, struct bstnode *root){ while(root!=NULL && value!=root->value) { if(value < root->value) root = root->left; else root = root->right; } return(root);}

Example 4: Apply search operation in the Binary tree using Recursive function

struct btnode *search(int item, struct btnode *root){ if(root==NULL || item == root->value) return(root); if(item < root->info) return recursive_search(item, root->left); else return recursive_search(item, root->right);}

Example 5: Examine whether the given binary tree is Binary Search Tree

bool isbst(struct btnode* root,int min,int max){ if(root==NULL) return true; if(n->data<=min || n->data > max) return false; if(!isbst(root->left,min,n->data) || !isbst(root->right,n->data,max)) return false; return true;}

Example 6: Write a recursive function to count the number of nodes in binary tree

int count(stuct btnode* root) { if(root == NULL) return 0; else return count(root->left) + count(root->right) + 1;}

AVL Trees

A BST is said to be an AVL tree if and only if each node in the tree satisfies the following property:
  • The difference in the height of the left subtree and the right subtree should be less than our equal to 1. 
  • Every subtree of the tree should also follow all properties of an AVL tree.

An AVL (Adelson-Velski and Landis) is a binary tree with the following properties.

  • For any node in the tree, the difference between height of the left subtree and the right subtree should be 1.
  • The height of an empty subtree in AVL tree is –1.
  • Every node in an AVL tree is associated with a height balance factor.
  • Balance factor (BF) of node = Height of left subtree – Height of right subtree
  • A node with balance factor – 1, 0 or 1 is stated as balanced AVL tree.
  • AVL Tree is height balanced binary tree.
  • Our main objective is to keep the binary tree always balanced with n given nodes so that the height of the tree never exceeds O(log n).
  • After every insertion or deletion we must ensure that the tree is balanced.
  • A search in the balanced binary tree is equivalent to a binary search in an ordered list.
  • In both the cases, checking each time eliminates half of the remaining items. Hence, complexity of searching is O(log n).
  • AVL tree with n nodes has height equals to O(log(n)).
  • For search/insert/delete operations takes worst-case time of O(log(n)).
Rotations: A rotation in tree is required when we insert or delete a node which makes the tree unbalanced. 

Left rotation (L-rotation): Left rotation of nodes can be depicted from the below diagrams.

Left Rotation

Right rotation (R-rotation): Right rotation of nodes can be depicted from the below diagrams.

Right rotation

Double right-left rotation (R-L rotation):

RL

Double right-left rotation (L-R rotation):

LR

A non-empty binary tree T is said to be n  AVL-tree if and only if it has this balance factor. 

|h(TL) – h(TR)| ≤ 1

where, h(TL) = Height of left subtree TL of tree T, and h(TR) = Height of right subtree TR of tree T

h(TL) – h(TR) is known as Balance Factor (BF).

For an height balanced AVL tree, the balance factor can be either 0, 1 or –1.

Insertion of a node into AVL tree

  • Insert a node finding its suitable place (position) by using BST property. 
  • Calculate the balance factor for each node.
  • Balance the AVL tree by using one of the four rotations if the tree becomes imbalanced.

Deletion of a node into AVL tree

  • Delete a node with BST delete procedure.
  • If the tree is imbalanced balance the AVL tree using AVL rotations.

Minimum number of nodes an AVL tree can have with height h:

Let, N(h) be the minimum number of nodes an AVL tree can have with height h.

N(0)=1, N(1)=2, N(2)=4, and

  • In general, N(h) = 1 + N(h−1) + N(h−2)

A tree with height h must have at least one child bearing height  of h−1, and to make the tree as small as possible, we make the other child have height h−2.

  • N(h) = F(h+2) - 1, where F(n) gives the nth Fibonacci number.
Maximum number of nodes (n) an AVL tree can have with height h is:
  • n = 2h+1 – 1
 
Example: Insert the following elements 1, 2, 3, 4, 5, 6, 7 into an empty AVL tree.
 
Insert 1,2:
1-2
 

Insert 3: (left rotation requires after inserting 3 as a right child to 2)

3

Insert 4:

4

Insert 5: (left rotation is required after inserting 5 as right child to 4)

5

Insert 6:

6

Insert 7:  (left rotation required after inserting 7 as right child to 6)

7  

These are the notes on BST and AVL trees. Now practice questions on these concepts.

Candidates can practice 110+ Mock Tests from the BYJU'S Exam Prep Test Series check the following link : 

Click Here to Avail GATE CSE Test Series!

You can follow the complete schedule for Champion study plan from the following link:

GATE 2021 CSE Detailed schedule for Champion study plan

Thanks

Prep Smart. Score Better!

 

Posted by:

Mukesh KumarMukesh KumarMember since Feb 2020
Share this article   |

Comments

write a comment
Load Previous Comments
Bachala Hari Prasad
Can someone cross check if L-R and R-L pictures pictures are correct
Pooja

PoojaNov 13, 2017

Is it sufficient notes to complete these topics??
Dinesh Kumar Kristam
Write BST (binary search tree)with deletion operations perform.50,70,60,20,90,10,40,100,30.
Pls answer quickly.....
Aaa

AaaFeb 20, 2018

One suggestion for gradeup : Please make the study materials like these readable.. in a nice format. I usually prefer geeksforgeeks to study. I find them better wrt study materials
...Read More
aswinos balaji
Is it only me who cant see the whole code. Rightmost area of the code i cant view. Or do others also have the same problem?
Shamlics

ShamlicsJul 24, 2018

Can someone please help with the following formula mentioned in the notes?
N(h) = F(h+2) - 1
Where h is the height of the tree; F is the fibonacci series.
If i work it out i end up getting N(h) = F(h+3) -1
...Read More
Coding Loop Hackers By Avanish
Sir please insert more and typictypical problem
Smn Afshn

Smn AfshnAug 7, 2019

The code is not movable... In phone not getting a complete view... Now it's slidable
Nandhini Rajavell
height of an empty subtree is –1. How ??

Follow us for latest updates