ASSIGNMENT WEEK – 6
Name – HIMANSHU RAJ
Register No. - EA2331201010152
Program - B.C.A.-Data Science
Subject – Data Structure & Algorithm (DSA)
Semester – II Semester
EA2331201010152
1. Explain the types of tree data structure with a neat diagram.
Ans. Tree Data Structures:
Trees are hierarchical non-linear data structures where nodes are connected in a parent-child relationship.
Each node can have zero or more children. They are useful for organizing and searching sorted data
efficiently.
Here are some common types of trees:
1. Binary Tree:
o A binary tree has a maximum of two children per node (left child and right child).
o The first node (without a parent) is called the root node.
o Binary trees are further classified based on additional properties:
▪ Full Binary Tree: Every node except leaves (leaf nodes have no children) has two
children.
▪ Complete Binary Tree: All levels are completely filled except possibly the last level,
which has all nodes filled in from the left side.
Diagram:
A (Root)
/ \
B C
/ \ /
D E F
2. Ternary Tree:
o A ternary tree allows a maximum of three children per node (left, middle, and right).
Diagram:
A (Root)
/ \ /
B C D
3. N-ary Tree (or Generic Tree):
o An n-ary tree allows a variable number of children per node.
Diagram:
A (Root)
/ \ / \
B C D E
/ \ \
F G H
4. Binary Search Tree (BST):
o A binary search tree is a special type of binary tree where each node's value is greater than all
its left children and less than all its right children.
o This property allows for efficient searching (average time complexity of O(log n)) and
ordering operations.
Diagram:
50 (Root)
/ \
EA2331201010152
30 70
/ \ / \
20 40 60 80
5. AVL Tree:
o An AVL tree is a self-balancing binary search tree.
o It maintains a height balance between left and right subtrees, ensuring efficient search and
insertion operations (guaranteed time complexity of O(log n)).
Diagram (AVL trees are more complex to visualize; the balance property is maintained during
operations):
30 (Root)
/ \
20 40
/ \ / \
10 25 35 50
6. Red-Black Tree:
o Another self-balancing binary search tree similar to AVL trees.
o It maintains balance using red and black color properties on nodes, ensuring logarithmic
search and insertion times.
Diagram (Similar to AVL Tree diagram):
30 (Root - Black)
/ \
20 (Red) 40 (Black)
/ \ / \
10 25 35 50 (Red)
7. B-Tree:
o A B-tree is a balanced m-way search tree (where m is a fixed branching factor) designed for
efficient disk storage and retrieval of data.
o It allows a node to have more than two children, improving search and insertion performance
for large datasets.
Diagram (B-Tree diagrams are more complex):
------- ------- ------- -------
| 3 | | 7 | | 12 | | 18 | (Root)
------- ------- ------- -------
/ \ / \
/ \ / \
------- ------- ------- -------
| 1 | | 2 | | 8 | | 10 |
------- ------- ------- -------
\ \ \
\ \ \
------- ------- -------
| 5 | | 9 | | 11 |
------- ------- -------
\ \
\ \
------- -------
| 6 | | 13 |
------- -------
These are some of the most common tree data structures. The choice of tree depends on the specific needs of
your application, such as data.
EA2331201010152
