ADS & A

Unit-2

Binary Search Tree

Definition:
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −
 The value of the key of the left sub-tree is less than the value of its parent (root) node's key.
 The value of the key of the right sub-tree is greater than or equal to the value of its parent (root)
node's key.
Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be
defined as –
left_subtree (keys) < node (key) ≤ right_subtree (keys)

Representation
BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a
key and an associated value. While searching, the desired key is compared to the keys in BST and if found,
the associated value is retrieved.
Following is a pictorial representation of BST –

We observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher
valued keys on the right sub-tree.
Basic Operations
Following are the basic operations of a tree –
1. Search − Searches an element in a tree.
2. Deletion – Delete an element in a tree
3. Insertion − Inserts an element in a tree.
4. Traversal
Pre-order Traversal − Traverses a tree in a pre-order manner.
In-order Traversal − Traverses a tree in an in-order manner.
Post-order Traversal − Traverses a tree in a post-order manner.
Node
Define a node having some data, references to its left and right child nodes.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
1. Search Operation
Whenever an element is to be searched, start searching from the root node. Then if the data is less than the
key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree.
Follow the same algorithm for each node.
Algorithm
struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");

while(current->data != data){

if(current != NULL) {
printf("%d ",current->data);

//go to left tree

if(current->data > data){
current = current->leftChild;
} //else go to right tree
else {
current = current->rightChild;
}

//not found
if(current == NULL){
return NULL;
}
}
}

return current;
}
2. Insert Operation
Whenever an element is to be inserted, first locate its proper location. Start searching from the root node,
then if the data is less than the key value, search for the empty location in the left subtree and insert the
data. Otherwise, search for the empty location in the right subtree and insert the data.
Algorithm
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;

tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;

//if tree is empty

if(root == NULL) {
root = tempNode;
} else {
 current = root;
parent = NULL;

while(1) {
parent = current;

//go to left of the tree

if(data < parent->data) {
current = current->leftChild;
//insert to the left

if(current == NULL) {
parent->leftChild = tempNode;
return;
}
} //go to right of the tree
else {
current = current->rightChild;

//insert to the right

if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}

3. Traversal:
Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are
connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access
a node in a tree. There are 2 ways which we use to traverse a tree −
1. Depth first traversal
2. Breadth first traversal (Level order traversal)
1. Depth first traversal
 In-order Traversal
 Pre-order Traversal
 Post-order Traversal
Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it
contains.
In-order Traversal
In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should
always remember that every node may represent a subtree itself.
If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.
We start from A, and following in-order traversal, we move to its left subtree B. B is also traversed in-
order. The process goes on until all the nodes are visited. The output of inorder traversal of this tree will be
−
D→B→E→A→F→C→G
Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.
Pre-order Traversal
In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.

We start from A, and following pre-order traversal, we first visit A itself and then move to its left
subtree B. B is also traversed pre-order. The process goes on until all the nodes are visited. The output of
pre-order traversal of this tree will be −
A→B→D→E→C→F→G
Algorithm
Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.
Post-order Traversal
In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then
the right subtree and finally the root node.

We start from A, and following Post-order traversal, we first visit the left subtree B. B is also traversed
post-order. The process goes on until all the nodes are visited. The output of post-order traversal of this tree
will be −
D→E→B→F→G→C→A
Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

2. Breadth First Search or Level order traversal

Level order traversal of a tree is the breadth first traversal of a tree which prints all the nodes of a tree level
by level.

Level order traversal : 27 14 35 10 19 31 42

AVL Tree
AVL Tree can be defined as height balanced binary search tree in which each node is associated with a
balance factor which is calculated by subtracting the height of its right sub-tree from that of its left sub-tree.
Tree is said to be balanced if balance factor of each node is in between -1 to 1, otherwise, the tree will be
unbalanced and need to be balanced.
Balance Factor (k) = height (left(k)) - height (right(k))
If balance factor of any node is 1, it means that the left sub-tree is one level higher than the right sub-tree.
If balance factor of any node is 0, it means that the left sub-tree and right sub-tree contain equal height.
If balance factor of any node is -1, it means that the left sub-tree is one level lower than the right sub-tree.
An AVL tree is given in the following figure. We can see that, balance factor associated with each node is in
between -1 and +1. therefore, it is an example of AVL tree.

Complexity
Algorithm Average case Worst case

Space o(n) o(n)

Search o(log n) o(log n)

Insert o(log n) o(log n)

 Delete o(log n) o(log n)

Operations on AVL tree

Due to the fact that, AVL tree is also a binary search tree therefore, all the operations are performed in the
same way as they are performed in a binary search tree. Searching and traversing do not lead to the violation
in property of AVL tree. However, insertion and deletion are the operations which can violate this property
and therefore, they need to be revisited.

SN Operation Description

1 Insertion Insertion in AVL tree is performed in the same way as it is performed in a binary
search tree. However, it may lead to violation in the AVL tree property and
therefore the tree may need balancing. The tree can be balanced by applying
rotations.

2 Deletion Deletion can also be performed in the same way as it is performed in a binary search
tree. Deletion may also disturb the balance of the tree therefore, various types of
rotations are used to rebalance the tree.

Why AVL Tree?

AVL tree controls the height of the binary search tree by not letting it to be skewed. The time taken for all
operations in a binary search tree of height h is O(h). However, it can be extended to O(n) if the BST
becomes skewed (i.e. worst case). By limiting this height to log n, AVL tree imposes an upper bound on
each operation to be O(log n) where n is the number of nodes.
AVL Rotations
We perform rotation in AVL tree only in case if Balance Factor is other than -1, 0, and 1. There are
basically four types of rotations which are as follows:
1. L L rotation: Inserted node is in the left subtree of left subtree of A
2. R R rotation : Inserted node is in the right subtree of right subtree of A
3. L R rotation : Inserted node is in the right subtree of left subtree of A
4. R L rotation : Inserted node is in the left subtree of right subtree of A
Where node A is the node whose balance Factor is other than -1, 0, 1.
The first two rotations LL and RR are single rotations and the next two rotations LR and RL are double
rotations. For a tree to be unbalanced, minimum height must be at least 2, Let us understand each rotation.
1. RR Rotation
When BST becomes unbalanced, due to a node is inserted into the right subtree of the right subtree of A,
then we perform RR rotation, RR rotation is an anticlockwise rotation, which is applied on the edge below a
node having balance factor -2
 In above example, node A has balance factor -2 because a node C is inserted in the right subtree of A right
subtree. We perform the RR rotation on the edge below A.
2. LL Rotation
When BST becomes unbalanced, due to a node is inserted into the left subtree of the left subtree of C, then
we perform LL rotation, LL rotation is clockwise rotation, which is applied on the edge below a node having
balance factor 2.

In above example, node C has balance factor 2 because a node A is inserted in the left subtree of C left
subtree. We perform the LL rotation on the edge below A.
3. LR Rotation
Double rotations are bit tougher than single rotation which has already explained above. LR rotation = RR
rotation + LL rotation, i.e., first RR rotation is performed on subtree and then LL rotation is performed on
full tree, by full tree we mean the first node from the path of inserted node whose balance factor is other than
-1, 0, or 1.

State Action

A node B has been inserted into the right subtree of A the left subtree of C, because of
which C has become an unbalanced node having balance factor 2. This case is L R
rotation where: Inserted node is in the right subtree of left subtree of C
 As LR rotation = RR + LL rotation, hence RR (anticlockwise) on subtree rooted at A is
performed first. By doing RR rotation, node A, has become the left subtree of B.

After performing RR rotation, node C is still unbalanced, i.e., having balance factor 2, as
inserted node A is in the left of left of C

Now we perform LL clockwise rotation on full tree, i.e. on node C. node C has now
become the right subtree of node B, A is left subtree of B

Balance factor of each node is now either -1, 0, or 1, i.e. BST is balanced now.

Let us understand each and every step very clearly:

4. RL Rotation
State Action

A node B has been inserted into the left subtree of C the right subtree of A, because of
which A has become an unbalanced node having balance factor - 2. This case is RL
rotation where: Inserted node is in the left subtree of right subtree of A
 As RL rotation = LL rotation + RR rotation, hence, LL (clockwise) on subtree rooted
at C is performed first. By doing RR rotation, node C has become the right subtree of B.

After performing LL rotation, node A is still unbalanced, i.e. having balance factor -2,
which is because of the right-subtree of the right-subtree node A.

Now we perform RR rotation (anticlockwise rotation) on full tree, i.e. on node A.

node C has now become the right subtree of node B, and node A has become the left
subtree of B.

Balance factor of each node is now either -1, 0, or 1, i.e., BST is balanced now.

As already discussed, that double rotations are bit tougher than single rotation which has already explained
above. R L rotation = LL rotation + RR rotation, i.e., first LL rotation is performed on subtree and then RR
rotation is performed on full tree, by full tree we mean the first node from the path of inserted node whose
balance factor is other than -1, 0, or 1.
Q: Construct an AVL tree having the following elements
H, I, J, B, A, E, C, F, D, G, K, L
1. Insert H, I, J
On inserting the above elements, especially in the case of H, the BST becomes unbalanced as the Balance
Factor of H is -2. Since the BST is right-skewed, we will perform RR Rotation on node H.
The resultant balance tree is:

2. Insert B, A
On inserting the above elements, especially in case of A, the BST becomes unbalanced as the Balance
Factor of H and I is 2, we consider the first node from the last inserted node i.e. H. Since the BST from H is
left-skewed, we will perform LL Rotation on node H.
The resultant balance tree is:

3. Insert E
On inserting E, BST becomes unbalanced as the Balance Factor of I is 2, since if we travel from E to I we
find that it is inserted in the left subtree of right subtree of I, we will perform LR Rotation on node I. LR =
RR + LL rotation
3 a) We first perform RR rotation on node B
The resultant tree after RR rotation is:

3b) We first perform LL rotation on the node I

The resultant balanced tree after LL rotation is:
4. Insert C, F, D

On inserting C, F, D, BST becomes unbalanced as the Balance Factor of B and H is -2, since if we travel
from D to B we find that it is inserted in the right subtree of left subtree of B, we will perform RL Rotation
on node I. RL = LL + RR rotation.
4a) We first perform LL rotation on node E
The resultant tree after LL rotation is:
4b) We then perform RR rotation on node B
The resultant balanced tree after RR rotation is:

5. Insert G
On inserting G, BST become unbalanced as the Balance Factor of H is 2, since if we travel from G to H, we
find that it is inserted in the left subtree of right subtree of H, we will perform LR Rotation on node I. LR =
RR + LL rotation.
5 a) We first perform RR rotation on node C
The resultant tree after RR rotation is:

5 b) We then perform LL rotation on node H

The resultant balanced tree after LL rotation is:

6. Insert K
On inserting K, BST becomes unbalanced as the Balance Factor of I is -2. Since the BST is right-skewed
from I to K, hence we will perform RR Rotation on the node I.
The resultant balanced tree after RR rotation is:

7. Insert L
On inserting the L tree is still balanced as the Balance Factor of each node is now either, -1, 0, +1. Hence the
tree is a Balanced AVL tree
Applications Of AVL Trees
1. AVL trees are mostly used for in-memory sorts of sets and dictionaries.
2. AVL trees are also used extensively in database applications in which insertions and deletions are
fewer but there are frequent lookups for data required.
3. It is used in applications that require improved searching apart from the database applications.

B Tree
B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can have at
most m-1 keys and m children. One of the main reason of using B tree is its capability to store large number
of keys in a single node and large key values by keeping the height of the tree relatively small.
A B tree of order m contains all the properties of an M way tree. In addition, it contains the following
properties.
1. Every node in a B-Tree contains at most m children.
2. Every node in a B-Tree except the root node and the leaf node contain at least m/2 children.
3. The root nodes must have at least 2 nodes.
4. All leaf nodes must be at the same level.
It is not necessary that, all the nodes contain the same number of children but, each node must have m/2
number of nodes.
A B tree of order 4 is shown in the following image.
While performing some operations on B Tree, any property of B Tree may violate such as number of
minimum children a node can have. To maintain the properties of B Tree, the tree may split or join.
Operations
Searching :
Searching in B Trees is similar to that in Binary search tree. For example, if we search for an item 49 in the
following B Tree. The process will something like following :
1. Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-tree.
2. Since, 40<49<56, traverse right sub-tree of 40.
3. 49>45, move to right. Compare 49.
4. match found, return.
Searching in a B tree depends upon the height of the tree. The search algorithm takes O(log n) time to search
any element in a B tree.

Inserting
Insertions are done at the leaf node level. The following algorithm needs to be followed in order to insert an
item into B Tree.
1. Traverse the B Tree in order to find the appropriate leaf node at which the node can be inserted.
2. If the leaf node contain less than m-1 keys then insert the element in the increasing order.
3. Else, if the leaf node contains m-1 keys, then follow the following steps.
o Insert the new element in the increasing order of elements.
o Split the node into the two nodes at the median.
 o Push the median element upto its parent node.
o If the parent node also contain m-1 number of keys, then split it too by following the same
steps.
Example:
Insert the node 8 into the B Tree of order 5 shown in the following image.

8 will be inserted to the right of 5, therefore insert 8.

The node, now contain 5 keys which is greater than (5 -1 = 4 ) keys. Therefore split the node from
the median i.e. 8 and push it up to its parent node shown as follows.

Deletion
Deletion is also performed at the leaf nodes. The node which is to be deleted can either be a leaf node or an
internal node. Following algorithm needs to be followed in order to delete a node from a B tree.
1. Locate the leaf node.
2. If there are more than m/2 keys in the leaf node then delete the desired key from the node.
3. If the leaf node doesn't contain m/2 keys then complete the keys by taking the element from eight or
left sibling.
o If the left sibling contains more than m/2 elements then push its largest element up to its
parent and move the intervening element down to the node where the key is deleted.
o If the right sibling contains more than m/2 elements then push its smallest element up to the
parent and move intervening element down to the node where the key is deleted.
4. If neither of the sibling contain more than m/2 elements then create a new leaf node by joining two
leaf nodes and the intervening element of the parent node.
5. If parent is left with less than m/2 nodes then, apply the above process on the parent too.
If the the node which is to be deleted is an internal node, then replace the node with its in-order successor or
predecessor. Since, successor or predecessor will always be on the leaf node hence, the process will be
similar as the node is being deleted from the leaf node.
Example 1
Delete the node 53 from the B Tree of order 5 shown in the following figure.

53 is present in the right child of element 49. Delete it.

Now, 57 is the only element which is left in the node, the minimum number of elements that must be present
in a B tree of order 5, is 2. it is less than that, the elements in its left and right sub-tree are also not sufficient
therefore, merge it with the left sibling and intervening element of parent i.e. 49.
The final B tree is shown as follows.

UNIT-2 10 MARKS QUESTIONS:

1. Create a binary search tree for the following numbers start from an empty binary search tree.
45,26,10,60,70,30,40 Delete keys 10,60 and 45 one after the other and show the trees at each stage.
2. How to insert and delete an element into a binary search tree and write down the code for the
insertion routine with an example
3. Construct an expression tree for the expression (a+b*c) + ((d*e+f)*g). Give the outputs when you
apply inorder, preorder and postorder traversals.
4. Explain the tree traversal techniques with an example.
5. Explain the AVL tree insertion and deletion with suitable example.
6. Describe the algorithms used to perform single and double rotation on AVL tree.
7. Explain about B-Tree with suitable example.
8. Describe about height balanced trees and B.trees with suitable illustration.
9. Explain Breadth First Search algorithm with example?
10. Explain Depth first and breadth first traversal?
11. Write an algorithm for binary search with suitable example.
 12. Define binary search tree with example?

13. State the operations on binary search tree?

14. Compare binary tree and binary search tree?

15. List the applications of Trees?

UNIT-2 2-MARKS QUESTIONS:

1. Define a tree
Ans: A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of a
distinguished node r, called the root, and zero or more nonempty (sub) trees T1, T2,…,Tk, each of whose
roots are connected by a directed edge from r.
2. Define root
Ans: This is the unique node in the tree to which further sub-trees are attached.

Here, A is the root.

3. Define degree of the node
Ans: The total number of sub-trees attached to that node is called the degree of the
node.

For node A, the degree is 2 and for B and C, the degree is 0.

4. Define leaves
Ans: These are the terminal nodes of the tree. The nodes with degree 0 are always the
leaves.

Here, B and C are leaf nodes.

5. Define internal nodes
Ans: The nodes other than the root and the leaves are called internal nodes.

Here, C is the internal node.

6. Define parent node
Ans: The node which is having further sub-branches is called the parent node of those sub-
branches.

Here, node C is the parent node of D and E

7. Define depth and height of a node

Ans: For any node ni, the depth of ni is the length of the unique path from the root to ni. The height of
ni is the length of the longest path from ni to a leaf.

8. Define depth and height of a tree

Ans: The depth of the tree is the depth of the deepest leaf. The height of the tree is equal to
the height of the root. Always depth of the tree is equal to height of the tree.

9. What do you mean by level of the tree?

Ans: The root node is always considered at level zero, then its adjacent children are supposed to
be at level 1 and so on.
Here, node A is at level 0, nodes B and C are at level 1 and nodes D and E are at
level 2.

10. Define a binary tree

Ans: A binary tree is a finite set of nodes which is either empty or consists of a root and two
disjoint binary trees called the left sub-tree and right sub-tree.

11. Define a path in a tree

Ans: A path in a tree is a sequence of distinct nodes in which successive nodes are connected by
edges in the tree.

12. Define a full binary tree

Ans: A full binary tree is a tree in which all the leaves are on the same level and every non-leaf
node has exactly two children.

13. Define a complete binary tree

Ans: A complete binary tree is a tree in which every non-leaf node has exactly two children not
necessarily to be on the same level.

14. State the properties of a binary tree

Ans:
a. The maximum number of nodes on level n of a binary tree is 2n-1, where n≥1.
b. The maximum number of nodes in a binary tree of height n is 2n-1, where n≥1.
c. For any non-empty tree, nl=nd+1 where nl is the number of leaf nodes and nd is the number
of nodes of degree 2.
15. What is meant by binary tree traversal?
Ans: Traversing a binary tree means moving through all the nodes in the binary tree, visiting each
node in the tree only once.
16. What are the different binary tree traversal techniques?
a. Preorder traversal
b. Inorder traversal
c. Postorder traversal
d. Levelorder traversal

17. What are the tasks performed during inorder traversal?

a. Traverse the left sub-tree
b. Process the root node
c. Traverse the right sub-tree

18. What are the tasks performed during postorder traversal?

a. Traverse the left sub-tree
b. Traverse the right sub-tree
c. Process the root node

19. Define a binary search tree

 Ans: A binary search tree is a special binary tree, which is either empty or it should satisfy the following
characteristics:
Every node has a value and no two nodes should have the same value i.e) the values
in the binary search tree are distinct
a. The values in any left sub-tree is less than the value of its parent node
b. The values in any right sub-tree is greater than the value of its parent node
c. The left and right sub-trees of each node are again binary search trees
20. Traverse the given tree using Inorder, Preorder and Postorder traversals.

Inorder : D H B E A F C I G J
Preorder: A B D H E C F G I J
Postorder: H D E B F I J G C A

21. Define AVL Tree.

Ans: AVL tree is a binary search tree which has the following properties:

1. The sub-trees of every node differ in height by at most one

2. Every sub-tree is an AVL tree. Search time is O(lon n) addition and deletion operations
also take O(log n) time

An empty tree is height balanced. If T is a non-empty binary tree with TL and TR as its left
and right subtrees, then T is height balanced if
i) TL and TR are height balanced and
ii) │hL - hR│≤ 1
Where hL and hR are the heights of TL and TR respectively.

22. What do you mean by balanced trees?

Ans: Balanced trees have the structure of binary trees and obey binary search tree properties. Apart from
these properties, they have some special constraints, which differ from one data structure to another.
However, these constraints are aimed only at reducing the height of the tree, because this factor
determines the time complexity.
Eg: AVL trees, Splay trees.

23.What are the categories of AVL rotations?

Ans: Let A be the nearest ancestor of the newly inserted nod which has the balancing factor ±2.
Then the rotations can be classified into the following four categories:
Left-Left: The newly inserted node is in the left subtree of the left child of A. Right-
Right: The newly inserted node is in the right subtree of the right child of
A. Left-Right: The newly inserted node is in the right subtree of the left child of A.
Right-Left: The newly inserted node is in the left subtree of the right child of A.

24.What do you mean by balance factor of a node in AVL tree?

Ans: The height of left subtree minus height of right subtree is called balance factor of a node in AVL
tree.The balance factor may be either 0 or +1 or -1.The height of an empty tree is -1.