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:
- Let k1 be the root node and k2 be its right child.
- After rotation, k2 becomes the new root.
- 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:
- Find the in-order successor (smallest node in the right subtree).
- Replace the value of the node to be deleted with the successor’s value.
- 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:
- Left-Right (LR) Rotation
- 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:
- Visit root node
- Visit nodes of level 2
- 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:
- Storing and searching sorted data
- Representing file systems in operating systems
- Implementing binary search trees and heaps
19. Basic Queue Operations
Answer:
- Enqueue(x) – Insert element at the rear of queue
- Dequeue() – Remove element from the front
- Front() – Returns front element without removing it
- 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:
- Linked lists do not require contiguous memory.
- Memory is allocated dynamically when needed.
- Insertion and deletion do not require shifting elements.
22. Priority Queue Uses
Answer:
Priority queues are used in:
- Operating system process scheduling
- Simulation programs
Elements with higher priority are processed first.
23. Uses of Queue
Answer:
Queues are used in:
- Simulation systems
- CPU scheduling
- Network packet handling
- Printer management
24. Evaluating Postfix Expressions
Answer:
Steps:
- Read operands and push them onto stack.
- When an operator appears, pop two operands.
- Perform the operation.
- 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.