Data structures are essential concepts in computer science and software engineering,

Data structures are essential concepts in computer science and software engineering, used to organize, manage, and store data efficiently. They provide a means to handle data in ways that facilitate efficient access and modification.

1. Introduction Data structures mainly specifies the following four things: Organization of data Accessing methods Degree of associativity Processing alternatives for information

2. Data structures can be classified into two main categories: Linear Data Structures : Arrays : Contiguous memory locations; fixed size. Linked Lists : Nodes containing data and a reference to the next node; dynamic size. Stacks : LIFO (Last In, First Out) structure. Queues : FIFO (First In, First Out) structure. 2. Non-Linear Data Structures : Trees : Hierarchical structure; nodes connected by edges. Examples: Binary Trees, Binary Search Trees, AVL Trees, B-Trees. Graphs : Consist of vertices (nodes) and edges; can be directed or undirected. Examples: Directed Graphs, Undirected Graphs, Weighted Graphs.

3. Linear Data Structures: Array : Static, fixed size, efficient random access. Linked List : Dynamic size, efficient insertions/deletions. Stack : Supports operations at one end (top). Queue : Supports operations at both ends (front and rear).

4. Non-Linear Data Structures: Tree : Root node, hierarchical structure. Binary Tree : Each node has at most two children. Binary Search Tree : Left child < root < right child. AVL Tree : Self-balancing binary search tree. B-Tree : Balanced tree for disk storage. Graph : Consists of vertices connected by edges. Directed Graph : Edges have directions. Undirected Graph : Edges have no direction. Weighted Graph : Edges have weights.

5. The maximum number of nodes in a tree for which post-order and pre-order traversals may be equal is: a) 3 b) 1 c) 2 d) any number Answer: b) 1

6. Pre-order Traversal : Visit the root node, then recursively visit the left subtree, and finally the right subtree. Post-order Traversal : Recursively visit the left subtree, then the right subtree, and finally visit the root node. For a tree with only one node (the root), both pre-order and post-order traversals would simply visit this single node, making the traversals equal. However, if the tree has more than one node, the traversals will differ because: In pre-order, the root is visited first. In post-order, the root is visited last. A tree with 2 nodes: Pre-order: root, child Post-order: child, root Even with just one child, the traversals differ. Therefore, the maximum number of nodes for which pre-order and post-order traversals can be equal is only 1.

7. The pre-order and in-order traversals of a binary tree are T M L N P O Q and L M N T O P Q respectively. What is the post-order traversal? a) L N M O Q P T b) N M O P O L T c) L M N O P Q T d) O P L M N Q T Answer: a) L N M O Q P T

8. To determine the post-order traversal from given pre-order and in-order traversals, follow the below steps: Pre-order Traversal: T M L N P O Q In-order Traversal: L M N T O P Q Identify the Root: In pre-order traversal, the first element is the root. Hence, T is the root. Divide In-order Traversal: Locate T in the in-order sequence: L M N T O P Q. Elements left of T (L M N) are in the left subtree. Elements right of T (O P Q) are in the right subtree. 3. Repeat for Subtrees: Left Subtree: Pre-order: M L N In-order: L M N Root is M. Split in-order as L M N. Left of M: L, Right of M: N.

9. Right Subtree : Pre-order: P O Q In-order: O P Q Root is P. Split in-order as O P Q. Left of P: O, Right of P: Q. 4. Construct Post-order: For Left Subtree (root M): L N M For Right Subtree (root P): O Q P Combine with root T: L N M O Q P T So, the post-order traversal is L N M O Q P T , which corresponds to option (a) .

10. What is a full binary tree? Each node has exactly zero or two children b) Each node has exactly two children c) All the leaves are at the same level d) Each node has exactly one or two children Answer: a) Each node has exactly zero or two children

11. In a binary search tree, which of the following traversals would print the numbers in ascending order? Level-order traversal Pre-order traversal Post-order traversal In-order traversal Answer: d) In-order traversal

12. What is the time complexity of level-order traversal? O(1) O(n) O(log n) O(n log n) Answer: b) O(n)

13. The time complexity of a level-order traversal of a binary tree is O(n)O(n)O(n), where nnn is the number of nodes in the tree. Level-order traversal involves visiting each node level by level from the root down to the deepest level. This traversal typically uses a queue to keep track of nodes at each level. Starting from the root, each node is enqueued, and its children are processed. Each node is visited exactly once, and each enqueue and dequeue operation on the queue takes constant time