CS301 – Data Structures

1. Complete Binary Tree

Answer:
A complete binary tree is a binary tree in which every internal node has exactly two children and every leaf node has no children.

2. Binary Tree

Answer:
A binary tree is a data structure that consists of nodes where each node has at most two children, called the left child and right child.
The top node is called the root, and the remaining nodes form the left and right subtrees.

3. Difference Between Binary Tree and AVL Tree

Answer:

Binary Tree	AVL Tree
A tree where each node has at most two children	A self-balancing Binary Search Tree
No restriction on height difference	Height difference between left and right subtree is at most 1
May become unbalanced	Always balanced

4. Single Left Rotation in AVL Tree

Answer:
Single left rotation is used to balance a tree when the right subtree becomes heavier.

Steps:

1. Let k1 be the root node and k2 be its right child.
2. After rotation, k2 becomes the new root.
3. k1 becomes the left child of k2.

This operation restores the balance of the AVL tree.

5. Height of a Tree

Answer:
The height of a tree is the maximum number of levels from the root node to the deepest leaf node.

6. Balance of a Node

Answer:
The balance factor of a node is calculated as:

Balance Factor = Height of Left Subtree – Height of Right Subtree

If the balance factor is -1, 0, or +1, the node is considered balanced.

7. Why Queue is a Linear Data Structure

Answer:
A queue is a linear data structure because elements are arranged in a sequential order.
Insertion is done at the rear and deletion is done from the front.

Queue follows the FIFO (First In First Out) principle.

8. Deleting a Node with Two Children in a Binary Search Tree

Answer:
To delete a node with two children in a BST:

1. Find the in-order successor (smallest node in the right subtree).
2. Replace the value of the node to be deleted with the successor’s value.
3. Delete the successor node.

9. Const Keyword

Answer:
The const keyword is used to declare a variable whose value cannot be changed after initialization.

10. Reference Variable

Answer:
A reference variable is another name for an existing variable.
It refers to the same memory location as the original variable.

11. Dangling Reference

Answer:
A dangling reference occurs when a pointer or reference points to a memory location that has already been deleted or deallocated.

12. How to Avoid Dangling Reference

Answer:
To avoid dangling references:

• Do not return references of local variables from functions.
• Ensure that references always point to valid memory locations.

13. Queue length() Method

Answer:
The length() method returns the number of elements currently stored in the queue, not the size of the internal array.

14. Double Rotation in AVL Tree

Answer:
Double rotation is used when a single rotation cannot balance the tree.

Two cases:

1. Left-Right (LR) Rotation
2. Right-Left (RL) Rotation

15. Level Order Traversal of Tree

Answer:
Level order traversal visits tree nodes level by level starting from the root.

Process:

1. Visit root node
2. Visit nodes of level 2
3. Visit nodes of level 3 and so on

A queue data structure is used to perform level order traversal.

16. Maximum Comparisons During BST Insertion

Answer:
If the tree is complete or nearly complete, the maximum number of comparisons required is:

log₂(n)

where n is the number of nodes.

17. Function Call Stack

Answer:
A function call stack is used to manage function calls in a program.
It stores:

• Function parameters
• Return addresses
• Local variables

18. Applications of Binary Tree

Answer:
Binary trees are used for:

1. Storing and searching sorted data
2. Representing file systems in operating systems
3. Implementing binary search trees and heaps

19. Basic Queue Operations

Answer:

1. Enqueue(x) – Insert element at the rear of queue
2. Dequeue() – Remove element from the front
3. Front() – Returns front element without removing it
4. isEmpty() – Checks if queue is empty

20. Benefit of Using Stack

Answer:
A stack follows the LIFO (Last In First Out) principle and is useful for:

• Managing function calls
• Expression evaluation
• Undo operations in programs

21. Why Linked Lists Waste Less Memory Than Arrays

Answer:

1. Linked lists do not require contiguous memory.
2. Memory is allocated dynamically when needed.
3. Insertion and deletion do not require shifting elements.

22. Priority Queue Uses

Answer:
Priority queues are used in:

1. Operating system process scheduling
2. Simulation programs

Elements with higher priority are processed first.

23. Uses of Queue

Answer:
Queues are used in:

1. Simulation systems
2. CPU scheduling
3. Network packet handling
4. Printer management

24. Evaluating Postfix Expressions

Answer:

Steps:

1. Read operands and push them onto stack.
2. When an operator appears, pop two operands.
3. Perform the operation.
4. Push the result back onto stack.

25. Empty Stack

Answer:
An empty stack means that there are no elements in the stack.
The function isEmpty() returns true when the stack is empty.