1. What is a tree?

A tree is also one of the data structures that represent hierarchical data. Suppose we
want to show the employees and their positions in the hierarchical form then it can
be represented as shown below:

2. What are the basic terminologies of tree?

In the above structure, each node is labeled with some number. Each arrow shown
in the above figure is known as a link between the two nodes.
o Root: The root node is the topmost node in the tree hierarchy. In other
words, the root node is the one that doesn't have any parent. In the above
structure, node numbered 1 is the root node of the tree. If a node is directly
linked to some other node, it would be called a parent-child relationship.
o Child node: If the node is a descendant of any node, then the node is known
as a child node.
o Parent: If the node contains any sub-node, then that node is said to be the
parent of that sub-node.
o Sibling: The nodes that have the same parent are known as siblings.
o Leaf Node:- The node of the tree, which doesn't have any child node, is
called a leaf node. A leaf node is the bottom-most node of the tree. There
can be any number of leaf nodes present in a general tree. Leaf nodes can
also be called external nodes.
o Internal nodes: A node has atleast one child node known as an internal
o Ancestor node:- An ancestor of a node is any predecessor node on a path
from the root to that node. The root node doesn't have any ancestors. In the
tree shown in the above image, nodes 1, 2, and 5 are the ancestors of node
10.
o Descendant: The immediate successor of the given node is known as a
descendant of a node. In the above figure, 10 is the descendant of node 5.

3. What are the properties of tree?

 Recursive data structure: The tree is also known as a recursive data

structure. A tree can be defined as recursively because the distinguished
node in a tree data structure is known as a root node.

 Number of edges: If there are n nodes, then there would n-1 edges. Each
arrow in the structure represents the link or path. Each node, except the root
node, will have atleast one incoming link known as an edge. There would be
one link for the parent-child relationship.
 Depth of node x: The depth of node x can be defined as the length of the
path from the root to the node x. One edge contributes one-unit length in the
path. So, the depth of node x can also be defined as the number of edges
between the root node and the node x. The root node has 0 depth.
 Height of node x: The height of node x can be defined as the longest path
from the node x to the leaf node.

4. How to declare a tree?

struct node
{
int data;
struct node *left;
struct node *right;
}

The above structure can only be defined for the binary trees because the binary
tree can have utmost two children, and generic trees can have more than two
children. The structure of the node for generic trees would be different as
compared to the binary tree.

5. What are the applications of tree?

The following are the applications of trees:

o Storing naturally hierarchical data: Trees are used to store the data in the
hierarchical structure. For example, the file system. The file system stored
on the disc drive, the file and folder are in the form of the naturally
hierarchical data and stored in the form of trees.
o Organize data: It is used to organize data for efficient insertion, deletion
and searching. For example, a binary tree has a logN time for searching an
element.
o Trie: It is a special kind of tree that is used to store the dictionary. It is a fast
and efficient way for dynamic spell checking.
o Heap: It is also a tree data structure implemented using arrays. It is used to
implement priority queues.
o B-Tree and B+Tree: B-Tree and B+Tree are the tree data structures used to
implement indexing in databases.
o Routing table: The tree data structure is also used to store the data in
routing tables in the routers.

6. What are the types of tree in data structure?

a) General tree: The general tree is one of the types of tree data structure. In
the general tree, a node can have either 0 or maximum n number of nodes.
There is no restriction imposed on the degree of the node (the number of
nodes that a node can contain). The topmost node in a general tree is known
as a root node. The children of the parent node are known as subtrees.

b) Binary tree: Here, binary name itself suggests two numbers, i.e., 0 and 1. In
a binary tree, each node in a tree can have utmost two child nodes. Here,
utmost means whether the node has 0 nodes, 1 node or 2 nodes.

c) Binary Search tree: Binary search tree is a non-linear data structure in which
one node is connected to n number of nodes. It is a node-based data
structure. A node can be represented in a binary search tree with three fields,
i.e., data part, left-child, and right-child. A node can be connected to the
utmost two child nodes in a binary search tree, so the node contains two
pointers (left child and right child pointer).

7. What are the types of tree with respect to nodes?

a) Binary tree:
A binary Tree is defined as a Tree data structure with at most 2 children. Since
each element in a binary tree can have only 2 children, we typically name them the
left and right child.
b) 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”.

c) N-ary 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.

8. Explain in detail on binary tree.

The Binary tree means that the node can have maximum two children. Here, binary
name itself suggests that 'two'; therefore, each node can have either 0, 1 or 2
children.
Properties of Binary tree:

o At each level of i, the maximum number of nodes is 2i.

o The height of the tree is defined as the longest path from the root node to the
leaf node. The tree which is shown above has a height equal to 3. Therefore,
the maximum number of nodes at height 3 is equal to (1+2+4+8) = 15. In
general, the maximum number of nodes possible at height h is (2 0 + 21 + 22+
….2h) = 2h+1 -1.
o The minimum number of nodes possible at height h is equal to h+1.
o If the number of nodes is minimum, then the height of the tree would be
maximum. Conversely, if the number of nodes is maximum, then the height
of the tree would be minimum.

Binary tree implementation

struct node
{
int data,
struct node *left, *right;
}
In the above structure, data is the value, left pointer contains the address of the
left node, and right pointer contains the address of the right node.

Binary tree traversal:

1. Inorder :

Following are the steps required for the inorder traversal:

o Visit all the nodes in the left subtree

o Visit the root node
o Visit all the nodes in the right subtree
Linear data structures such as stack, array, queue, etc., only have one way to
traverse the data. But in hierarchical data structures such as tree, there are multiple
ways to traverse the data. Here we will discuss another way to traverse the tree
data structure, i.e., inorder traversal.

Example of inorder traversal

Now, let's see an example of inorder traversal. It will be easier to understand the
procedure of inorder traversal using an example.
The nodes with yellow color are not visited yet. Now, we will traverse the nodes of
the above tree using inorder traversal.

o Here, 40 is the root node. We move to the left subtree of 40, that is 30, and it
also has subtree 25, so we again move to the left subtree of 25 that is 15.
Here, 15 has no subtree, so print 15 and move towards its parent node, 25.
o Now, print 25 and move to the right subtree of 25.

o Now, print 28 and move to the root node of 25 that is 30.

o So, left subtree of 30 is visited. Now, print 30 and move to the right child of
30.

o Now, print 35 and move to the root node of 30.

o Now, print root node 40 and move to its right subtree.

o Now recursively traverse the right subtree of 40 that is 50.

50 have subtree so first traverse the left subtree of 50 that is 45. 45 has no
children, so print 45 and move to its root node.
o Now print 50 and move to the right subtree of 50 that is 60.

o Now recursively traverse the right subtree of 50 that is 60. 60 have subtree
so first traverse the left subtree of 60 that is 55. 55 has no children, so print
55 and move to its root node.
o Now print 60 and move to the right subtree of 60 that is 70.

o Now print 70.

After the completion of inorder traversal, the final output is -

{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
2. Preorder:
In preorder traversal, first, root node is visited, then left sub-tree and after that right
sub-tree is visited. The process of preorder traversal can be represented as -
root → left → right
Root node is always traversed first in preorder traversal, while it is the last item of
postorder traversal. Preorder traversal is used to get the prefix expression of a tree.

Example of preorder traversal

Now, let's see an example of preorder traversal. It will be easier to understand the
process of preorder traversal using an example.

The nodes with yellow color are not visited yet. Now, we will traverse the nodes of
the above tree using preorder traversal.
o Start with the root node 40. First, print 40 and then recursively traverse the
left subtree.

o Now, move to the left subtree. For left subtree, the root node is 30. Print 30,
and move towards the left subtree of 30.
o In left subtree of 30, there is an element 25, so print 25, and traverse the left
subtree of 25.

o In left subtree of 25, there is an element 15, and 15 has no subtree. So, print
15, and move to the right subtree of 25.
o In right subtree of 25, there is 28, and 28 has no subtree. So, print 28, and
move to the right subtree of 30.

o In right subtree of 30, there is 35 that has no subtree. So print 35, and
traverse the right subtree of 40.
o In the right subtree of 40, there is 50. Print 50, and traverse the left subtree
of 50.

o In the left subtree of 50, there is 45 that do not have any child. So, print 45,
and traverse the right subtree of 50.
o In right subtree of 50, there is 60. Print 60 and traverse the left subtree of
60.

o In the left subtree of 60, there is 55 that does not have any child. So, print
55 and move to the right subtree of 60.
o In the right subtree of 60, there is 70 that do not have any child. So, print
70 and stop the process.

After the completion of preorder traversal, the final output is -

40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70

3. Postorder:
The postorder traversal is one of the traversing techniques used for visiting the
node in the tree. It follows the principle LRN (Left-right-node). Postorder
traversal is used to get the postfix expression of a tree.

The following steps are used to perform the postorder traversal:

o Traverse the left subtree by calling the postorder function recursively.

o Traverse the right subtree by calling the postorder function recursively.
o Access the data part of the current node.

Example of postorder traversal

Now, let's see an example of postorder traversal. It will be easier to understand the
process of postorder traversal using an example.

The nodes with yellow color are not visited yet. Now, we will traverse the nodes of
above tree using postorder traversal.

o Here, 40 is the root node. We first visit the left subtree of 40, i.e., 30. Node
30 will also traverse in post order. 25 is the left subtree of 30, so it is also
traversed in post order. Then 15 is the left subtree of 25. But 15 has no
subtree, so print 15 and move towards the right subtree of 25.

o 28 is the right subtree of 25, and it has no children. So, print 28.
o Now, print 25, and the postorder traversal for 25 is finished.

o Next, move towards the right subtree of 30. 35 is the right subtree of 30, and
it has no children. So, print 35.
o After that, print 30, and the postorder traversal for 30 is finished. So, the left
subtree of given binary tree is traversed.

o Now, move towards the right subtree of 40 that is 50, and it will also
traverse in post order. 45 is the left subtree of 50, and it has no children.
So, print 45 and move towards the right subtree of 50.
o 60 is the right subtree of 50, which will also be traversed in post order. 55 is
the left subtree of 60 that has no children. So, print 55.

o Now, print 70, which is the right subtree of 60.

o Now, print 60, and the post order traversal for 60 is completed.

o Now, print 50, and the post order traversal for 50 is completed.
o At last, print 40, which is the root node of the given binary tree, and the
post order traversal for node 40 is completed.

The final output that we will get after postorder traversal is -

{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}

9. What is threaded binary tree (2m)

A threaded binary tree is a type of binary tree data structure where the empty left
and right child pointers in a binary tree are replaced with threads that link nodes
directly to their in-order predecessor or successor, thereby providing a way to
traverse the tree without using recursion or a stack.
10.Explain in detail on Binary search tree.
A binary search tree follows some order to arrange the elements. In a Binary search
tree, the value of left node must be smaller than the parent node, and the value of
right node must be greater than the parent node. This rule is applied recursively to
the left and right subtrees of the root.

Advantages of Binary Search tree:

o Searching an element in the Binary search tree is easy as we always have a
hint that which subtree has the desired element.
o As compared to array and linked lists, insertion and deletion operations are
faster in BST.

Example of creating a Binary search tree:

Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50

o First, we have to insert 45 into the tree as the root of the tree.
o Then, read the next element; if it is smaller than the root node, insert it as the
root of the left subtree, and move to the next element.
o Otherwise, if the element is larger than the root node, then insert it as the
root of the right subtree.
Now, let's see the process of creating the Binary search tree using the given data
element. The process of creating the BST is shown below -

Step 1 - Insert 45.

Step 2 - Insert 15.

As 15 is smaller than 45, so insert it as the root node of the left subtree.
Step 3 - Insert 79.

As 79 is greater than 45, so insert it as the root node of the right subtree.

Step 4 - Insert 90.

90 is greater than 45 and 79, so it will be inserted as the right subtree of 79.

Step 5 - Insert 10.

10 is smaller than 45 and 15, so it will be inserted as a left subtree of 15.

Step 6 - Insert 55.

55 is larger than 45 and smaller than 79, so it will be inserted as the left subtree of
79.

Step 7 - Insert 12.

12 is smaller than 45 and 15 but greater than 10, so it will be inserted as the right
subtree of 10.
Step 8 - Insert 20.

20 is smaller than 45 but greater than 15, so it will be inserted as the right subtree
of 15.

Step 9 - Insert 50.

50 is greater than 45 but smaller than 79 and 55. So, it will be inserted as a left
subtree of 55.

Now, the creation of binary search tree is completed.

Searching in Binary Search Tree:

Searching means to find or locate a specific element or node in a data structure. In

Binary search tree, searching a node is easy because elements in BST are stored in
a specific order. The steps of searching a node in Binary Search tree are listed as
follows -

1. First, compare the element to be searched with the root element of the tree.
2. If root is matched with the target element, then return the node's location.
3. If it is not matched, then check whether the item is less than the root
element, if it is smaller than the root element, then move to the left subtree.
4. If it is larger than the root element, then move to the right subtree.
5. Repeat the above procedure recursively until the match is found.
6. If the element is not found or not present in the tree, then return NULL.
Now, let's understand the searching in binary tree using an example. We are taking
the binary search tree formed above. Suppose we have to find node 20 from the
below tree.

Step1:

Step2:

Step3:
Deletion in Binary Search tree:

In a binary search tree, we must delete a node from the tree by keeping in mind
that the property of BST is not violated. To delete a node from BST, there are three
possible situations occur -

o The node to be deleted is the leaf node, or,

o The node to be deleted has only one child, and,
o The node to be deleted has two children
We will understand the situations listed above in detail.

When the node to be deleted is the leaf node

It is the simplest case to delete a node in BST. Here, we have to replace the leaf
node with NULL and simply free the allocated space.

We can see the process to delete a leaf node from BST in the below image. In
below image, suppose we have to delete node 90, as the node to be deleted is a leaf
node, so it will be replaced with NULL, and the allocated space will free.
When the node to be deleted has only one child

In this case, we have to replace the target node with its child, and then delete the
child node. It means that after replacing the target node with its child node, the
child node will now contain the value to be deleted. So, we simply have to replace
the child node with NULL and free up the allocated space.

We can see the process of deleting a node with one child from BST in the below
image. In the below image, suppose we have to delete the node 79, as the node to
be deleted has only one child, so it will be replaced with its child 55.

So, the replaced node 79 will now be a leaf node that can be easily deleted.

When the node to be deleted has two children

This case of deleting a node in BST is a bit complex among other two cases. In
such a case, the steps to be followed are listed as follows -

o First, find the inorder successor of the node to be deleted.

o After that, replace that node with the inorder successor until the target node
is placed at the leaf of tree.
o And at last, replace the node with NULL and free up the allocated space.
The inorder successor is required when the right child of the node is not empty. We
can obtain the inorder successor by finding the minimum element in the right child
of the node.

We can see the process of deleting a node with two children from BST in the
below image. In the below image, suppose we have to delete node 45 that is the
root node, as the node to be deleted has two children, so it will be replaced with its
inorder successor. Now, node 45 will be at the leaf of the tree so that it can be
deleted easily.

Insertion in Binary Search Tree

A new key in BST is always inserted at the leaf. To insert an element in BST, we
have to start searching from the root node; if the node to be inserted is less than the
root node, then search for an empty location in the left subtree. Else, search for the
empty location in the right subtree and insert the data. Insert in BST is similar to
searching, as we always have to maintain the rule that the left subtree is smaller
than the root, and right subtree is larger than the root.

Now, let's see the process of inserting a node into BST using an example.
11.Explain in detail on 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))

Operation of AVL Tree:

SN Operatio Description
n

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
1 Insertion
property and therefore the tree may need balancing. The tree can be
balanced by applying rotations.

Deletion can also be performed in the same way as it is performed in a

2 Deletion binary search tree. Deletion may also disturb the balance of the tree
therefore, various types of rotations are used to rebalance the tree.

Rotation of AVL tree:

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.

12.What is a heap tree?

A Heap is a complete binary tree data structure that satisfies the heap property: for
every node, the value of its children is greater than or equal to its own value. Heaps
are usually used to implement priority queues, where the smallest (or largest)
element is always at the root of the tree.

Min Heap: The value of the parent node should be less than or equal to either of
its children.
Max Heap: The value of the parent node is greater than or equal to its children.

13.Explain in detail on 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.
Operations of B tree:

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.

Else, if the leaf node c

Advertisement

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.

Advertisement

1.

ontains 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.

nsert 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.

Applications of B tree:

B tree is used to index the data and provides fast access to the actual data stored on
the disks since, the access to value stored in a large database that is stored on a disk
is a very time consuming process.

14.Explain in detail on B+ tree.

B+ Tree is an extension of B Tree which allows efficient insertion, deletion and

search operations.

In B Tree, Keys and records both can be stored in the internal as well as leaf nodes.
Whereas, in B+ tree, records (data) can only be stored on the leaf nodes while
internal nodes can only store the key values.

The leaf nodes of a B+ tree are linked together in the form of a singly linked lists
to make the search queries more efficient.

B+ Tree are used to store the large amount of data which can not be stored in the
main memory. Due to the fact that, size of main memory is always limited, the
internal nodes (keys to access records) of the B+ tree are stored in the main
memory whereas, leaf nodes are stored in the secondary memory.
The internal nodes of B+ tree are often called index nodes. A B+ tree of order 3 is
shown in the following figure.

Advantages of B+ Tree

1. Records can be fetched in equal number of disk accesses.

2. Height of the tree remains balanced and less as compare to B tree.
3. We can access the data stored in a B+ tree sequentially as well as directly.
4. Keys are used for indexing.
5. Faster search queries as the data is stored only on the leaf nodes.

Insertion in B+ Tree
Step 1: Insert the new node as a leaf node

Step 2: If the leaf doesn't have required space, split the node and copy the middle
node to the next index node.

Step 3: If the index node doesn't have required space, split the node and copy the
middle element to the next index page.

Example :

Insert the value 195 into the B+ tree of order 5 shown in the following figure.
195 will be inserted in the right sub-tree of 120 after 190. Insert it at the desired
position.

The node contains greater than the maximum number of elements i.e. 4, therefore
split it and place the median node up to the parent.

Now, the index node contains 6 children and 5 keys which violates the B+ tree
properties, therefore we need to split it, shown as follows.
Deletion in B+ Tree
Step 1: Delete the key and data from the leaves.

Step 2: if the leaf node contains less than minimum number of elements, merge
down the node with its sibling and delete the key in between them.

Step 3: if the index node contains less than minimum number of elements, merge
the node with the sibling and move down the key in between them.

Example

Delete the key 200 from the B+ Tree shown in the following figure.
200 is present in the right sub-tree of 190, after 195. delete it.

Merge the two nodes by using 195, 190, 154 and 129.
Now, element 120 is the single element present in the node which is violating the
B+ Tree properties. Therefore, we need to merge it by using 60, 78, 108 and 120.

Now, the height of B+ tree will be decreased by 1.