CSE-1207: Data Structure Final Exam –

Algorithm Study Guide

1. Trees
Definition

A tree is a hierarchical structure with nodes. It starts with a root node, and each node can
have child nodes. Each connection is a parent-child relationship.

Tree Height Algorithm

1. If the current node is null, return -1.

2. Recursively calculate the height of the left subtree.
3. Recursively calculate the height of the right subtree.
4. Return the maximum of the two heights plus 1.

Tree Size Algorithm

1. If the current node is null, return 0.

2. Recursively calculate the size of the left subtree.
3. Recursively calculate the size of the right subtree.
4. Return 1 plus the sizes of the left and right subtrees.

Tree Traversals

1. In-order: Traverse left, visit root, traverse right.

2. Pre-order: Visit root, traverse left, traverse right.
3. Post-order: Traverse left, traverse right, visit root.
4. Level-order: Use queue. Enqueue root, then dequeue and enqueue children level-
wise.

• In-order (Left, Root, Right):

1. Traverse left subtree.
2. Visit root node.
3. Traverse right subtree.

• Pre-order (Root, Left, Right):

1. Visit root node.
2. Traverse left subtree.
3. Traverse right subtree.
 • Post-order (Left, Right, Root):
1. Traverse left subtree.
2. Traverse right subtree.
3. Visit root node.

• Level-order (Breadth-wise traversal):

1. Initialize a queue and enqueue the root.
2. While the queue is not empty:
▪ Dequeue a node and visit it.
▪ Enqueue its left child (if any).
▪ Enqueue its right child (if any).

2. Binary Search Trees (BST)

Properties

1. Left subtree has values less than the root.

2. Right subtree has values greater than the root.
3. No duplicates are typically allowed.

Height of BST

1. Same as Tree Height Algorithm.

Searching Algorithm

1. Start at the root node.

2. If the value matches the node, return found.
3. If the value is less, search left subtree.
4. If the value is greater, search right subtree.
5. If node is null, return value not found.

Insertion Algorithm

1. Start at root.
2. Compare value with current node.
3. If less, go left; if more, go right.
4. Insert node when null spot is found.

Deletion Algorithm

1. Case 1: Node has no children – remove it directly.

2. Case 2: Node has one child – replace it with its child.
 3. Case 3: Node has two children – find in-order successor, replace, and delete
successor.

3. Stacks
Definition

A linear structure that follows Last In First Out (LIFO) principle.

Basic Operations

• Push: Add element to the top.

• Pop: Remove top element.
• Peek: View top element without removing.
• IsEmpty: Check if stack is empty.

Stack Operations Using Array Implementation

• Push (Insert Element)

1. Check if top is equal to the maximum allowed index.

2. If yes, report overflow (stack is full).
3. If no, increment top by 1.
4. Place the new element at position top in the array.

• Pop (Remove Top Element)

1. Check if top is -1 (which means the stack is empty).

2. If yes, report underflow.
3. If no, access the element at position top.
4. Decrement top by 1.
5. Return the accessed element.

• Peek / Top (View Top Element)

1. Check if top is -1.

2. If yes, report that the stack is empty.
3. If no, return the element at index top.

• IsEmpty (Check if Stack is Empty)

1. If top is -1, return true.

2. Otherwise, return false.
Stack Operations Using Linked List Implementation

Each node in the stack has two fields: data and next. The top pointer points to the top
node of the stack.

• Push (Insert Element)

1. Create a new node.

2. Set the data of the new node to the value being pushed.
3. Set the next of the new node to point to the current top node.
4. Update the top pointer to point to the new node.

• Pop (Remove Top Element)

1. Check if top is null (stack is empty).

2. If yes, report underflow.
3. If no, store the current top node in a temporary pointer.
4. Move top to the next node (top = top->next).
5. Return the data of the removed node.
6. (Optionally) Free the memory of the removed node.

• Peek / Top (View Top Element)

1. Check if top is null.

2. If yes, report that the stack is empty.
3. If no, return the data stored in the top node.

• IsEmpty (Check if Stack is Empty)

1. If top is null, return true.

2. Otherwise, return false.

Balanced Brackets Algorithm

1. Use an empty stack.

2. Push opening brackets to stack.
3. Pop and match when closing bracket found.
4. If mismatch or unbalanced, return false.
5. If stack empty at end, brackets are balanced.
4. Infix, Prefix, Postfix
Postfix Evaluation

1. Use stack to store operands.

2. When operator appears, pop two operands.
3. Apply operation and push result back.
4. Final result is the top of the stack.

Infix to Postfix Conversion

1. Use stack for operators and list for output.

2. Operands go directly to output.
3. Push '(' to stack, pop till '(' when ')' appears.
4. Handle operator precedence and associativity.
5. Pop remaining operators to output at end.

5. Queues
Definition

A linear structure that follows First In First Out (FIFO) principle.

Basic Operations

• Enqueue: Add element at rear.

• Dequeue: Remove element from front.
• Peek: View front element.
• IsEmpty: Check if queue is empty.

Queue Operations Using Array Implementation

Enqueue Operation (Insert an element at the rear of the queue)

1. Check if the queue is full (if using array implementation).

2. If full, report overflow (or expand dynamically if allowed).
3. If empty, set both front and rear to 0.
4. Otherwise, increment rear by 1.
5. Insert the new element at the rear position.
Dequeue Operation (Remove an element from the front of the queue)

1. Check if the queue is empty.

2. If empty, report underflow (nothing to remove).
3. Access and store the element at the front.
4. If front equals rear, set both front and rear to -1 (queue becomes empty).
5. Otherwise, increment front by 1.
6. Return the stored element.

Peek / Front Operation (View the front element without removing it)

1. Check if the queue is empty.

2. If empty, report that the queue is empty.
3. Return the element at the front index.

IsEmpty Operation (Check if the queue has no elements)

1. Check if front is -1 or if front > rear (in case of dequeue operations).

2. If true, return true (queue is empty).
3. Else, return false (queue has elements).

Queue Operations Using Linked List Implementation

In this implementation, each node has two parts: data and next. The queue maintains
two pointers:
• front → points to the first node (to be dequeued next)
• rear → points to the last node (where new elements are enqueued)

1. Enqueue (Insert Element at Rear)

1. Create a new node.

2. Set the data field of the new node to the value to be inserted.
3. Set the next of the new node to null (it will be the last node).
4. If the queue is empty (front is null):
a. Set both front and rear to the new node.
5. Else:
a. Set rear->next to point to the new node.
b. Update rear to the new node.
 2. Dequeue (Remove Element from Front)

1. Check if the front is null (the queue is empty).

2. If yes, report underflow (nothing to remove).
3. Store the current front node in a temporary pointer.
4. Move the front pointer to the next node (front = front->next).
5. If front becomes null after the update, also set rear to null (queue is now empty).
6. Return the data of the removed node.
7. (Optionally) Free the memory of the removed node.

3. Peek / Front (View Front Element Without Removing)

1. Check if front is null.

2. If yes, report that the queue is empty.
3. Otherwise, return the data stored in the front node.

4. IsEmpty (Check if the Queue is Empty)

1. If front is null, return true.

2. Otherwise, return false.

Stack vs Queue – Detailed Comparison

1. Stack uses LIFO, Queue uses FIFO.

2. Stack elements are inserted and removed from the top, Queue uses both front and
rear.
3. Stack is suitable for recursive function calls, Queue is useful in scheduling and
buffering.
4. Stack operations are push/pop, Queue operations are enqueue/dequeue.
5. Stack is used in undo features, Queue is used in breadth-first search.