DATA STRUCTURES – 2nd ASSIGNMENT
Assignments Given Date: 24/03/2026
Collection Date Given: 28/03/2026
1) Construct a BST by inserting the elements: 60, 40, 80, 20, 50, 70, 90, 10, 30.
Write Preorder, Inorder, Postorder Traversals.
Step-by-Step BST Construction
Insert the elements one by one in the given order. In a Binary Search Tree (BST), values smaller than
the root are inserted to the left side, and values greater than the root are inserted to the right side.
60
/ \
40 80
/ \ / \
20 50 70 90
/ \
10 30
Explanation
60 becomes the root node.
40 is less than 60, so it is inserted to the left of 60.
80 is greater than 60, so it is inserted to the right of 60.
20 is less than 40, so it is inserted to the left of 40.
50 is greater than 40, so it is inserted to the right of 40.
70 is less than 80, so it is inserted to the left of 80.
90 is greater than 80, so it is inserted to the right of 80.
10 is less than 20, so it is inserted to the left of 20.
30 is greater than 20, so it is inserted to the right of 20.
Traversals
Preorder (Root → Left → Right): 60, 40, 20, 10, 30, 50, 80, 70, 90
Inorder (Left → Root → Right): 10, 20, 30, 40, 50, 60, 70, 80, 90
Postorder (Left → Right → Root): 10, 30, 20, 50, 40, 70, 90, 80, 60
2) Explain about B-Tree and its operations.
A B-Tree is a self-balancing multi-level search tree used to store sorted data efficiently. Unlike a
Binary Search Tree, a B-Tree node can contain multiple keys and multiple children. B-Trees are
widely used in databases and file systems because they reduce the number of disk accesses.
Basic Structure of B-Tree
[30 | 60]
/ | \
[10 20] [40 50] [70 80 90]
Properties of B-Tree
A B-Tree node can contain more than one key.
All leaf nodes are at the same level.
The tree remains balanced after insertion and deletion.
Searching, insertion, and deletion are efficient.
It is suitable for large amounts of data stored on disks.
Operations of B-Tree
1. Search Operation:
Start from the root node.
Compare the required key with keys in the current node.
If found, search is successful.
If not found, move to the appropriate child and continue.
2. Insertion Operation:
Insert the key into the correct leaf node.
If the node has space, insert directly.
If the node overflows, split the node into two parts.
Move the middle key to the parent node.
If the parent also overflows, repeat splitting upward.
3. Deletion Operation:
Delete the key from the node.
If the node still has enough keys, no problem.
If the node has fewer keys than required, borrow a key from a sibling or merge nodes.
The tree remains balanced after deletion.
3) Describe about Tree with its terminologies and types of binary trees.
A tree is a non-linear data structure made up of nodes connected by edges. It is used to represent
hierarchical relationships such as family trees, file systems, and organization charts.
General Tree Diagram
A
/ | \
B C D
/ \ |
E F G
Tree Terminologies
Node: Each element in the tree is called a node. Example: A, B, C.
Root Node: The topmost node of the tree. Example: A.
Parent Node: A node that has child nodes. Example: A is parent of B, C, D.
Child Node: A node directly connected below another node. Example: B is child of A.
Leaf Node: A node with no children. Example: E, F, C, G.
Edge: A connection between two nodes.
Degree of Node: Number of children of a node.
Level: Position of a node in the tree.
Height of Tree: Maximum number of edges from root to deepest leaf.
Subtree: A smaller tree formed from a node and its descendants.
Types of Binary Trees
A binary tree is a tree in which each node has at most two children: left child and right child.
1. Full Binary Tree
A
/ \
B C
/ \
D E
Every node has either 0 or 2 children.
2. Complete Binary Tree
A
/ \
B C
/ \ /
D E F
All levels are completely filled except possibly the last level, which is filled from left to right.
3. Perfect Binary Tree
A
/ \
B C
/ \ / \
D E F G
All internal nodes have 2 children and all leaf nodes are at the same level.
4. Skewed Binary Tree
A
\
B
\
C
\
D
All nodes are either on the left side or right side only.
5. Balanced Binary Tree
The height difference between left and right subtrees is minimal.
This improves search performance.
4) Explain the BST insertion algorithm with example. Explain B-Tree and its
characteristics.
BST Insertion Algorithm
Algorithm:
BST_INSERT(root, key)
1. If root is NULL:
Create a new node and return it
2. If key < [Link]:
[Link] = BST_INSERT([Link], key)
3. Else if key > [Link]:
[Link] = BST_INSERT([Link], key)
4. Return root
Example: Insert 45 into the BST
Before Insertion:
60
/ \
40 80
/ \
20 50
After Insertion of 45:
60
/ \
40 80
/ \
20 50
/
45
Explanation:
Start at root 60.
45 is less than 60, so move left to 40.
45 is greater than 40, so move right to 50.
45 is less than 50, so insert it to the left of 50.
B-Tree Characteristics
It is a balanced tree.
Each node can contain multiple keys.
It minimizes disk reads and writes.
All leaves are at the same level.
It is widely used in databases, indexing, and file systems.
5) Find the inorder, preorder and postorder traversal for the given tree.
Interpreted Tree Structure:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Traversal Rules
Preorder: Root → Left → Right
Inorder: Left → Root → Right
Postorder: Left → Right → Root
Answer
Preorder: 8, 3, 1, 6, 4, 7, 10, 14, 13
Inorder: 1, 3, 4, 6, 7, 8, 10, 13, 14
Postorder: 1, 4, 7, 6, 3, 13, 14, 10, 8
Conclusion
This assignment covers Binary Search Tree (BST), B-Tree, Tree Terminologies, Types of Binary
Trees, BST insertion algorithm, and Tree Traversals with proper diagrams and explanations.