CSU1051: Data Structures & Algorithms FAQ | Clearing Doubts with dmj.one

Frequently Asked Questions - Part 2

1. Stack

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. It has two major operations: push (insert an element onto the top of the stack) and pop (remove an element from the top of the stack).

Advantages:

Disadvantages:

Time Complexity:


// Stack implementation in C++
#include 
int main() {
std::stack s;
s.push(10); // Insert 10 onto the stack
s.pop(); // Remove top element from the stack
return 0;
}

2. Queue

A queue is a linear data structure that follows the First In First Out (FIFO) principle. It has two major operations: enqueue (insert an element at the end of the queue) and dequeue (remove an element from the front of the queue).

Advantages:

Disadvantages:

Time Complexity:


// Queue implementation in C++
#include 
int main() {
std::queue q;
q.push(10); // Insert 10 into the queue
q.pop(); // Remove the element from the front of the queue
return 0;
}

3. Deque (Double Ended Queue)

A deque is a type of queue that allows insertion and removal of elements from both the front and back. In a standard deque, no priority is assigned to elements, thus they can be inserted and deleted from both ends.

Advantages:

Disadvantages:

Time Complexity:


// Deque implementation in C++
#include 
int main() {
std::deque dq;
dq.push_back(10); // Insert 10 at the end
dq.push_front(20); // Insert 20 at the front
dq.pop_back(); // Remove the element from the end
dq.pop_front(); // Remove the element from the front
return 0;
}

4. Circular Queue

A circular queue is a variant of the linear queue which follows a circular shape. The last element points to the first making the queue behave like a circle.

Advantages:

Disadvantages:

Time Complexity:


// Circular Queue implementation in C++
#include 
class CircularQueue {
private:
int front, rear, size;
int* queue;

public:
CircularQueue(int size) {
front = rear = -1;
this->size = size;
queue = new int[size];
}
void enQueue(int value) {
    if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) {
        return;
    } else if (front == -1) {
        front = rear = 0;
        queue[rear] = value;
    } else if (rear == size-1 && front != 0) {
        rear = 0;
        queue[rear] = value;
    } else {
        rear++;
        queue[rear] = value;
    }
}

int deQueue() {
    if (front == -1) {
        return -1;
    }
    int temp = queue[front];
    if (front == rear) {
        front = -1;
        rear = -1;
    } else if (front == size-1) {
        front = 0;
    } else {
        front++;
    }
    return temp;
}
};

int main() {
CircularQueue q(5);
q.enQueue(10);
q.enQueue(20);
q.deQueue();
return 0;
}

5. Array

An array is a static linear data structure where elements are placed contiguous in memory. Elements in an array can be directly accessed using indices.

Advantages:

Disadvantages:

Time Complexity:


// Array implementation in C++
int main() {
    int array[5];  // Declaration of array
    array[0] = 10;  // Inserting 10 at 0th index
    array[1] = 20;  // Inserting 20 at 1st index
    return 0;
}

6. Linked List

A linked list is a dynamic linear data structure where each element is a separate object. Each element or node contains a pointer that points to the next node in the list.

Advantages:

Disadvantages:

Time Complexity:


// Linked List implementation in C++
struct Node {
    int data;
    Node* next;
};
int main() {
Node* head = new Node();
head->data = 10; // Inserting 10 at the head
head->next = NULL;
return 0;
}

7. Tree

A tree is a non-linear data structure with hierarchical relationships between its elements, known as nodes. Each node in a tree has a parent node and a set of child nodes. The node without a parent is the root of the tree.

Types of Trees:

Advantages:

Disadvantages:

Time Complexity:

The time complexity depends on the type of tree and the operation.

8. Binary Tree

A binary tree is a type of tree where each node can have at most two children, known as the left child and the right child.

Advantages:

Disadvantages:

Time Complexity:


// Binary Tree implementation in C++
struct Node {
    int data;
    Node* left;
    Node* right;
};
Node* newNode(int data) {
Node* node = new Node();
if (node == NULL) {
return NULL;
}
node->data = data;
node->left = node->right = NULL;
return node;
}

int main() {
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
return 0;
}

9. Binary Search Tree (BST)

A Binary Search Tree is a type of binary tree where the nodes are arranged in order: for each node, all elements in the left subtree are less-than the node, and all elements in the right subtree are greater-than the node.

Advantages:

Disadvantages:

Time Complexity:

However, in a 'balanced' binary search tree (AVL Trees, Red-Black Trees, etc), these operations can be performed in O(log n) time.


// Binary Search Tree implementation in C++
struct Node {
    int data;
    Node* left;
    Node* right;
};
// Function to create a new node
Node* newNode(int data) {
Node* node = new Node();
if (node == NULL) {
return NULL;
}
node->data = data;
node->left = node->right = NULL;
return node;
}

// Function to insert a node in a BST
Node* insert(Node* node, int data) {
if (node == NULL) {
return newNode(data);
}
if (data < node->data) {
node->left = insert(node->left, data);
} else if (data > node->data) {
node->right = insert(node->right, data);
}
return node;
}

int main() {
Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
return 0;
}

10. AVL Tree and Balance Factor

An AVL (Adelson-Velsky and Landis) tree is a self-balancing binary search tree in which the difference between the heights of the left and right subtrees (the balance factor) is not more than one for all nodes.

Balance factor of a node = height of left subtree - height of right subtree. If this factor is more than 1 or less than -1, the tree is unbalanced, and specific tree rotations are used to rebalance the tree.

Advantages:

Disadvantages:

Time Complexity:

11. Rotation Rules

Tree rotations are used in AVL trees to maintain their balance. There are four types of rotations: left-left, left-right, right-left, and right-right. The rotation type is determined by the 'heavy' side of the unbalanced node and its child.

12. Time Complexity

Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the program. It is usually expressed using Big O notation.

The most common time complexities are: O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), and O(2^n), which represent constant time, logarithmic time, linear time, linearithmic time, quadratic time, cubic time, and exponential time, respectively.

13. Calculating Maximum and Minimum Number of Nodes in a Tree

The minimum number of nodes in a tree of height h (height of root node = 1) can be calculated as h.

The maximum number of nodes in a tree of height h can be calculated as 2^h - 1.

In case of binary trees:

14. Typecasting

Typecasting, or type conversion, is a method of changing an entity from one data type to another. It is used in C++ for various purposes, such as to avoid loss of data, to add greater functionality to a program, or to convert objects of one class type into those of another class type.


// Typecasting in C++
int main() {
    double x = 10.3;
    int y;
    y = (int) x;  // This will assign the value 10 to y
    return 0;
}

15. BST Traversing (Pre, In, Post Order)

Tree traversal is a process of visiting (checking or updating) each node in a tree data structure, exactly once. In case of binary trees, they can be traversed in pre-order, in-order, and post-order.

15.1 Pre-order Traversal

In a pre-order traversal, the tree nodes are visited in the following order: Root, Left Subtree, Right Subtree.


void preOrder(Node* node) {
    if (node == NULL)
        return;
    cout << node->data << " ";
    preOrder(node->left);
    preOrder(node->right);
}

15.2 In-order Traversal

In an in-order traversal, the tree nodes are visited in the following order: Left Subtree, Root, Right Subtree.


void inOrder(Node* node) {
    if (node == NULL)
        return;
    inOrder(node->left);
    cout << node->data << " ";
    inOrder(node->right);
}

15.3 Post-order Traversal

In a post-order traversal, the tree nodes are visited in the following order: Left Subtree, Right Subtree, Root.


void postOrder(Node* node) {
    if (node == NULL)
        return;
    postOrder(node->left);
    postOrder(node->right);
    cout << node->data << " ";
}

16. Spanning Tree

A Spanning Tree of a connected, undirected graph is a subgraph that is a tree and connects (spans) all vertices of the graph. In a weighted graph, a Minimum Spanning Tree (MST) is a spanning tree that has minimum weight than all other spanning trees of the same graph.

Two popular algorithms to find the MST are Kruskal’s Minimum Spanning Tree Algorithm and Prim’s Minimum Spanning Tree Algorithm.

17. Linear vs Non-linear DS

In data structures, linear and non-linear data structures are the classifications based on the arrangement of data and the ability to change its position:

17.1 Linear Data Structures

Linear data structures have data elements arranged sequentially with each element connected to its previous and next element. The basic operations are performed in a linear order. Examples: Array, Stack, Queue, Linked List.

17.2 Non-linear Data Structures

Non-linear data structures have data elements arranged hierarchically, and each element can connect to two or more other elements, without a particular sequence. Examples: Trees and Graphs.

18. Types of Trees

Trees are a type of non-linear data structure that are used to represent hierarchical structure in a graphical form. Here are some common types of trees:

19. Quick Summary

19.1 Stack

A stack is essentially a list with the restriction that insertions and deletions can only be performed at one end. This end is known as the top. The element at the other end is known as the base. Stacks are useful in various algorithms where we need to temporarily store information and retrieve it in a LIFO manner.

LIFO structure. Main operations: push (add to top), pop (remove from top), peek (get top without removing it). Useful for reversing, backtracking, and parsing tasks. O(1) for main operations.

19.2 FIFO Structure

A queue is also a list, but with the condition that insertions are performed at one end (rear), while deletions are performed at the other end (front). It follows a FIFO pattern, making it useful in scenarios where we need to maintain the order of elements.

FIFO structure. Main operations: enqueue (add to rear), dequeue (remove from front). Useful in CPU scheduling, disk scheduling, data buffering. O(1) for main operations.

19.3 Deque (Double Ended Queue)

A Deque (Double Ended Queue) is a type of queue in which insertion and removal of elements can be performed from either from the front or rear. Thus, it does not follow the FIFO rule.

Insertion and deletion can be performed from either end. Combines capabilities of stacks and queues.

19.4 Circular Queue

A circular queue is a variant of the linear queue which follows a FIFO principle but with a twist: the last position is connected back to the first position making a circle. It efficiently utilizes memory that is freed after a dequeue operation.

Queue in a circular structure. Maximizes space utilization by using empty slots after dequeue operations.

19.5 Array

An array is a simple data structure used for storing an ordered list of items. The items can be the same type or different types. Arrays are useful when you need to access items by their numerical position in the list.

Fixed-size, contains elements of the same type. Random access possible, but insertions/deletions are costly due to shifting. O(1) for access, O(n) for insertion/deletion.

19.6 Linked List

A linked list is a dynamic data structure, in which data is not stored at contiguous memory locations. The concept of next points to the next node, and the last node points to null. A linked list is not suitable for direct access but efficient for insertions and deletions.

Dynamic size, contains nodes with data and link to next node. No random access but efficient insertions/deletions. O(n) for access/search, O(1) for insertion/deletion at head.

19.7 Tree

A tree is a hierarchical data structure that stores data in a sorted manner and enables search, insert, delete operations to be carried out efficiently. It's a powerful tool for organizing data in a natural hierarchy, such as a file system.

Hierarchical structure with a root node and children nodes. Used to represent hierarchical relationships, enable fast search/insert/delete operations.

19.8 Binary Tree

A binary tree is a tree-type non-linear data structure with a maximum of two children for each parent. The two children are usually differentiated as left child and right child. It is used in many algorithms due to its simple structure and ease of use.

Tree with a maximum of two children per node. Used in many algorithms for its simple structure.

19.9 Binary Search Tree (BST)

BST is a binary tree with a special property: each node has a value greater than all the values in its left subtree and less than all the values in its right subtree. This property provides a balance between the benefits of a sorted array and a linked list, allowing us to quickly search for, insert, and delete items.

Binary tree with left child node < parent node < right child node. Efficient search, insertion, deletion operations (O(log n) in ideal case).

19.10 AVL Tree (BST)

AVL tree is a self-balancing binary search tree, which means heights of two subtrees of any node differ by at most one. If at any point they differ by more than one, rebalancing is done to restore the property.

Self-balancing BST. Balance factor is the height of the left subtree - height of the right subtree and must be -1, 0, or 1. Balancing done via rotations.

19.11 Time Complexity

Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run, as a function of the length of the input. It is a theoretical estimate of the amount of time an algorithm needs to complete based on the size of the input.

Measures the time taken by an algorithm to run, as a function of the size of the input. Big O notation describes worst-case time complexity.

19.12 Calculating maximum and minimum number of nodes in a tree

In a binary tree of height 'h', the minimum number of nodes can be 'h' (if each level only has one node) and the maximum number of nodes can be 2^h - 1 (if each level is fully populated).

For a binary tree with 'h' height, min nodes = h, max nodes = 2^h - 1.

19.13 Typecasting

Typecasting is a way to convert a variable from one data type to another. This is used when you want to use a variable of one type as if it were a different type.

Converting a variable from one data type to another.

19.14 BST Traversing

Traversing is visiting every node in the BST. There are three common ways to traverse them in a depth-first order: Inorder (Left, Root, Right), Preorder (Root, Left, Right), and Postorder (Left, Right, Root).

Preorder (root, left, right), Inorder (left, root, right), Postorder (left, right, root).

19.15 Spanning Tree

In graph theory, a spanning tree T of a connected, undirected graph G is a tree that includes every vertex of G, with minimum possible number of edges.

Tree that includes all vertices of a graph. Minimum spanning tree (MST) is a spanning tree with minimum total edge weight.

19.16 Linear vs Non-linear Data Structures

Linear data structures have data elements arranged in a linear order where each element is connected to its previous and next element. Non-linear data structures are those data structures in which data elements are not in sequence, i.e., they are arranged hierarchically.

Linear - elements arranged in a sequence (Array, Stack, Queue, Linked List). Non-linear - hierarchical arrangement of elements (Trees, Graphs).