a)Explain doubly linked list and their characteristic?

Ans.The two-way linked list is also known as doubly linked list. In two- way linked
list or
doubly linked list, each node is divided into three parts Pre, Info, Next. The
structure of a
node used in two-way linked list is as shown below
 Pre part contains the address of preceding nodedoubly linked list is a data
structure in computer science that consists of a collection of nodes. Each node
contains three parts:

Data: The actual data or value that the node holds.

Pointer to the Next Node: A reference or pointer to the next node in the sequence.
Pointer to the Previous Node: A reference or pointer to the previous node in the
sequence.
In a doubly linked list, unlike a singly linked list, each node has pointers to
both its next node and its previous node. This bidirectional linking allows for
traversal in both forward and backward directions.
 Info part contains the element
 Next part contains the address of the next node
The Pre part of the first node of a two-way linked list will contain Null as there
is no node
preceding the first node. Similarly, the Next part of the last node of a two-way
linked list will
contain Null as there is no node following the last.
Characteristics of a doubly linked list:
 Each node contains two pointers: one pointing to the previous node and one
pointing to
the next node.  The first node’s previous pointer points to null and the last
node’s next pointer points to
null.  The linked list can be traversed in both forward and backward directions. 
The size of the linked list can be dynamically adjusted based on the number of
elements
added or removed.  Insertions and deletions can be performed in constant time at
both the beginning and the
end of the list.  It requires more memory compared to a singly linked list, as
each node has two pointers.
b)ADT for Trees and their applications.
Ans)A tree is a non-linear data structure used to represent the hierarchical
structure of one or more
elements known as nodes. Tree holds values and has either zero or more than zero
references which are referring to
other nodes known as child nodes. A tree can have zero or more child nodes, which
is at one
level below it and each child node can have only one parent node which above it.
The node at
the top of the tree is known as root of the tree and the node at the lowest level
is known as
leaf node. Ex: - a tree of an organization
Tree with one or more child nodes are called as internal nodes and the node without
child is
called as external nodes.
Applications of Trees:
 Hierarchical Management:- a tree like structure helps us to understand the
protocol
easily. Example:-Board of management.  Effortlessness searching:- as data is in
sorted manner so searching is easier compare
to other linear data structures. Example: - searching a file in Linux.  Easy
Manipulations:- as data is two linear so can be used to process. Example: - sorting
according to date_of _joining
c)Draw binary tree whoe preorder and inrorder are:)
MAM HAS NOT SEND THE PDF...
d)Explain Binary Search Tree
Ans) Binary search tree (BST) is a very important subclass of binary trees.  In
binary trees data is not ordered in some logical order but in BST, data is managed
in
such a logical way that it can be retrieved efficiently when required.  A binary
search tree is a binary tree in which node containing the data has the following
constraints:
 Each data element in the left subtree is less than its root element.  Each data
element in the right subtree is greater than or equal to its root element.  Both
the left and right subtree of the root will be again a BST
Benefits of using binary search tree
1. Searching become very efficient in a binary search tree since, we get a hint at
each step, about which sub-tree contains the preferred element. 2. The binary
search tree is considered as well-organized data structure in compare to arrays
and linked lists. In searching process, it removes half sub-tree at every step. 3.
It also speed up the insertion and deletion operations as compare to that in array
and linked list.
e)Write a short note on Heap
Ans)A binary heap is a heap data structure that takes the form of a binary tree.
Binary heaps are a
common way of applying priority queues. The binary heap was announced by J. W. J.
Williams in 1964. A binary heap is defined as a binary tree with two constraints:-
Form property: a binary heap is a complete binary tree and all levels of the tree,
except
possibly the last one are fully filled, and, if the last level of the tree is not
complete, the nodes
of that level are filled from left.
There are two types of heaps:
1. If the value present in any node is greater than all its children then such a
tree is called
as the max-heap or descending heap. 2. In min-heap or ascending heap the value
present at any node is smaller than all its
children.
f)Make a binary search tree by inserting the following numbers in sequence
52 36 98 29 123 39 15 56 31 365 278 45 72
SOLVE IT BY YOUR OWN AND LEMME KNOW
g)Explain Huffman Algorithms.
Ans)Huffman code: decoding
• Huffman invented in 1952 a greedy algorithm for constructing an optimal prefix
code, called a Huffman code. • Decoding:
1. Start at the root of the coding tree T, read input bits. 2.After reading “0” go
left
3.After reading “1” go right
4. If a leaf node has been reached, output the character stored in the leaf, and
return to the
root of the tree.
Huffman coding is a lossless data compression algorithm. The idea is to assign
variable-length codes to input characters, lengths of the assigned codes are based
on the frequencies of corresponding characters.
The variable-length codes assigned to input characters are Prefix Codes, means the
codes (bit sequences) are assigned in such a way that the code assigned to one
character is not the prefix of code assigned to any other character. This is how
Huffman Coding makes sure that there is no ambiguity when decoding the generated
bitstream.
Let us understand prefix codes with a counter example. Let there be four characters
a, b, c and d, and their corresponding variable length codes be 00, 01, 0 and 1.
This coding leads to ambiguity because code assigned to c is the prefix of codes
assigned to a and b. If the compressed bit stream is 0001, the de-compressed output
may be “cccd” or “ccb” or “acd” or “ab”.
The method which is used to construct optimal prefix code is called Huffman coding.
This algorithm builds a tree in bottom up manner. We can denote this tree by T
h)List any 5 and Explain properties of Binary Tree.
Ans)1. Root – The mother node at the top of the tree is called root. There is only
one root per
tree and one path from the root node to any node.
2. Path− Path refers to the sequence of nodes along the edges of a tree.
3. Node− Every individual element in tree is called as node. Every information is
stored in
the node with the value and link to other nodes.
4. Parent node− Any node excluding the root node has one edge upward to a node
called
parent node.
5. Child node− The node below a given node connected by its edge downward is called
its
child node.
i)Explain Sequential Representation of Binary Tree.
Ans)Sequential Representation:
 Root of tree is always stored at the 1st array index & its left and right child
will be
stored at 2nd and 3rdindex respectively.  If a node occupies the Kth
index of array then its:- o Left child will be stored at (2 × k)
th array index. o Right child will be stored at (2 × (k + 1))
th array index.  Sequential representation of binary tree of height h will require
an array size 2(h+1)-1
j)Write a short note on Heap. Explain its types.
Ans)PLEASE REFER TO QUESTION.e) OF UNIT TWO
k)What is Doubly linked list? How to traverse a doubly linked list?
Ans)doubly linked list is a data structure in computer science that consists of a
collection of nodes. Each node contains three parts:
Data: The actual data or value that the node holds.
Pointer to the Next Node: A reference or pointer to the next node in the sequence.
Pointer to the Previous Node: A reference or pointer to the previous node in the
sequence.
In a doubly linked list, unlike a singly linked list, each node has pointers to
both its next node and its previous node. This bidirectional linking allows for
traversal in both forward and backward directions.
To traverse a doubly linked list, you can start from the head node (the first node
in the list) and follow the pointers in both directions until you reach the end of
the list
In a doubly linked list, each node has two pointers: next, which points to the next
node in the list, and previous, which points to the previous node in the list. This
allows you to traverse the list in both forward and backward directions
l) Draw max and min heap with the following elements
80 59 25 30 100 45 62 89 51 23 11 27 323
NOT DONE YET....😁