DSA Revision Notes: 7 Worked Questions on Search, Stacks, Trees and Graphs

Reading a definition is different from solving a question. This DSA revision set makes you trace indices, stacks, queue positions and tree changes on paper. Use it after the Data Structures core notes. It is a practice companion, not a replacement for the full subject.

These are original worked questions for general BTech CSE revision. They are not previous-year questions or predictions. Match the topics to your own syllabus. The examples use zero-based array indices, distinct BST keys and explicitly stated queue rules.

Pocket reference: choose the right structure

Structure	Rule	Check before using
Stack	Last in, first out	Underflow before popping
Queue	First in, first out	Full/empty convention and wrap
BST	Left keys smaller, right keys larger	Height: a plain BST is not always balanced
Hash table	Hash picks a starting slot	Collisions, capacity and deletion markers
BFS	Queue explores by distance in edges	Unweighted graph; mark when enqueuing
DFS	Recursion or stack explores deeply	Visited set and neighbor order

1. Count the work before naming the complexity

Question: How many times does the inner statement execute?

for i = 0 to n - 1:
    for j = 0 to i:
        do constant-time work

For i = 0, it runs once. For i = 1, it runs twice. The counts are 1, 2, 3, ..., n, so the total is n(n + 1)/2. For n = 5, that is 15 executions. Its tight asymptotic bound is Theta(n squared), assuming each inner operation takes constant time.

Trap: Two loops do not automatically mean quadratic time. If both loops independently visit every element one after the other, the work is n + n, which is linear. If one loop repeatedly doubles its index until it reaches n, it has logarithmically many iterations. Look at the bounds and updates, not just the number of loops.

2. Binary search: write low, high and mid

Question: Find 23 in the sorted array [3, 7, 11, 18, 23, 31, 44]. Use inclusive low/high bounds and mid = low + floor((high - low)/2).

Step	low	high	mid / value	Action
1	0	6	3 / 18	23 is larger: low = 4
2	4	6	5 / 31	23 is smaller: high = 4
3	4	4	4 / 23	Found at index 4

For a missing value such as 20, step 3 compares with 23 and sets high = 3. Now low = 4 is greater than high = 3, so stop: not found. This implementation makes at most logarithmically many comparisons because each step removes roughly half the remaining range.

Answer check: State that the array is sorted. Use mid + 1 or mid - 1 when discarding the compared position; otherwise a missing value can leave the same range forever. If duplicate values exist, this basic search may find any matching occurrence, not necessarily the first.

3. Postfix evaluation: operand order matters

Question: Evaluate the space-separated postfix expression 8 3 2 * - 4 +.

Token	Action	Stack, bottom to top
8	Push	8
3	Push	8, 3
2	Push	8, 3, 2
*	3 * 2 = 6	8, 6
-	8 - 6 = 2	2
4	Push	2, 4
+	2 + 4 = 6	6

At a binary operator, the first popped item is the right operand and the second is the left operand. Subtraction and division expose this mistake: 8 - 6 is not 6 - 8. A valid expression must have enough operands at each operator and exactly one final result. Tokenization also matters; a multi-digit number is one token, not two separate operands.

4. Circular queue: fix the convention first

Question: Trace a queue of capacity 4. Here front is the next removal index, rear is the next insertion index, and count stores the number of live items. Initially all three are 0.

1. Enqueue 10, 20, 30: array positions 0, 1, 2 hold those values. front = 0, rear = 3, count = 3.
2. Dequeue: return 10. front becomes (0 + 1) mod 4 = 1; count = 2.
3. Enqueue 40 at index 3: rear becomes 0; count = 3.
4. Enqueue 50 at index 0: rear becomes 1; count = 4.

The logical queue is now 20, 30, 40, 50. Both front and rear equal 1, but it is full, not empty. In this convention, count = 0 means empty and count = capacity means full. Reject another enqueue until space becomes available.

Trap: Some textbooks reserve one unused slot instead of storing count, and some define rear as the last occupied position. Do not mix their full/empty conditions with these formulas. State your convention before tracing.

5. Delete a two-child node from a BST

Question: Insert 40, 20, 60, 10, 30, 50, 70 into a basic BST, then delete 40 using its inorder successor.

Before deletion:
        40
       /  \
     20    60
    / \   / \
   10 30 50 70

After deletion:
        50
       /  \
     20    60
    / \     \
   10 30    70

The successor is the smallest key in the right subtree: 50. Replace the root key with 50 and remove the original 50 node from the right subtree. Do not leave two copies. The inorder result is 10, 20, 30, 50, 60, 70, which checks the ordering.

Leaf deletion removes the leaf. One-child deletion connects the parent to that child. Two-child deletion needs a replacement and a second removal. Search, insertion and deletion depend on height: a balanced tree has logarithmic height, while sorted insertions into a naive BST can produce a linear chain. Inorder traversal still visits all nodes.

6. Linear probing: a collision is not a lost key

Question: An empty hash table has 7 slots. Use h(k) = k mod 7 and linear probing. Insert 10, 17, 24 and 9.

• 10 hashes to 3: store it at slot 3.
• 17 hashes to 3: slot 3 is occupied, so use slot 4.
• 24 hashes to 3: slots 3 and 4 are occupied, so use slot 5.
• 9 hashes to 2: use slot 2.

To find 24, check slots 3, 4 and 5 with the same probe sequence. When deleting 17, simply turning slot 4 into a normal empty slot can break a search that stops at the first empty slot. This scheme can use a tombstone, or another correct deletion method, so later keys remain searchable. A tombstone is not the same as a never-used empty slot.

Answer check: Show the probe positions, wrap with modulo capacity, and bound the number of probes so a full table cannot cause an endless loop. Collisions are expected; performance depends on the hash function, occupancy and collision-handling rules.

7. BFS and DFS: state the neighbor order

Draw the graph before tracing it

        D
        |
        B ----- E
       /         \
      A           F
       \         /
        C -------
Edges: A-B, A-C, B-D, B-E, C-F, E-F

The graph is undirected: each edge appears in both endpoint lists. From A, BFS discovers B and C before their children. Recursive DFS follows B first, then returns after finishing that branch. The visited set prevents the cycle A-B-E-F-C-A from causing repeated visits.

Use this undirected graph, with neighbors visited alphabetically:

A: B, C
B: A, D, E
C: A, F
D: B
E: B, F
F: C, E

BFS from A: Mark a vertex when it enters the queue. Removing A discovers B and C. Removing B discovers D and E. Removing C discovers F. The visit order is A, B, C, D, E, F. The first-discovery parent of F is C, so the path A-C-F has two edges.

Recursive DFS from A: Visit A, then B, then D. Return to B, visit E, then F, then C. The order is A, B, D, E, F, C. A different neighbor order can produce a different valid traversal. DFS does not generally find the fewest-edge path.

BFS gives shortest paths by edge count in an unweighted graph. For unequal edge weights, that is not the same as minimum total weight. Both traversals take O(V + E) with adjacency lists when each vertex and edge is processed a bounded number of times. If the graph is disconnected, restart from unvisited vertices to cover it all.

Run the seven answers, do not just memorize them

This Python verification program was executed. It checks all seven topics, including both successful and unsuccessful binary search. The small arrays and graph are the exact examples above, not a benchmark. The BST functions assume distinct keys.

from collections import deque
print("loop n=5:", sum(1 for i in range(5) for j in range(i + 1)))

def search(a, target):
    low, high, trace = 0, len(a)-1, []
    while low <= high:
        mid = low + (high-low)//2
        trace.append((low, high, mid))
        if a[mid] == target: return mid, trace
        if a[mid] < target: low = mid+1
        else: high = mid-1
    return -1, trace
print("search 23:", search([3,7,11,18,23,31,44], 23))
print("search 20:", search([3,7,11,18,23,31,44], 20))
stack=[]
for token in "8 3 2 * - 4 +".split():
    if token.lstrip('-').isdigit(): stack.append(int(token))
    else:
        right, left = stack.pop(), stack.pop()
        stack.append({'*':lambda:left*right, '-':lambda:left-right,
                      '+':lambda:left+right}[token]())
assert len(stack)==1
print("postfix result:", stack[0])
buf=[None]*4; front=rear=count=0
for op, val in [('in',10),('in',20),('in',30),('out',None),('in',40),('in',50)]:
    if op=='in':
        assert count<4
        buf[rear]=val; rear=(rear+1)%4; count+=1
    else:
        assert count>0
        buf[front]=None; front=(front+1)%4; count-=1
print("queue:", [buf[(front+i)%4] for i in range(count)], "front/rear/count:", front,rear,count)

def insert(t, key):
    if t is None: return [key,None,None]
    side=1 if key<t[0] else 2
    t[side]=insert(t[side],key)
    return t

def delete(t,key):
    if t is None: return None
    if key<t[0]: t[1]=delete(t[1],key)
    elif key>t[0]: t[2]=delete(t[2],key)
    elif t[1] is None: return t[2]
    elif t[2] is None: return t[1]
    else:
        successor=t[2]
        while successor[1] is not None: successor=successor[1]
        t[0]=successor[0]; t[2]=delete(t[2],successor[0])
    return t

def inorder(t):
    return inorder(t[1])+[t[0]]+inorder(t[2]) if t else []
tree=None
for key in [40,20,60,10,30,50,70]: tree=insert(tree,key)
tree=delete(tree,40)
print("BST after delete 40:", inorder(tree))
table=[None]*7
for key in [10,17,24,9]:
    for offset in range(7):
        i=(key%7+offset)%7
        if table[i] is None: table[i]=key; break
    else: raise ValueError("full table")
print("hash slots:", table)
graph={'A':['B','C'],'B':['A','D','E'],'C':['A','F'],
       'D':['B'],'E':['B','F'],'F':['C','E']}
queue=deque(['A']); seen={'A'}; bfs=[]; parent={'A':None}
while queue:
    v=queue.popleft(); bfs.append(v)
    for w in graph[v]:
        if w not in seen: seen.add(w); queue.append(w); parent[w]=v
seen=set(); dfs=[]
def visit(v):
    seen.add(v); dfs.append(v)
    for w in graph[v]:
        if w not in seen: visit(w)
visit('A')
print("BFS:", ' '.join(bfs), "; F parent:", parent['F'])
print("DFS:", ' '.join(dfs))

Executed output:

loop n=5: 15
search 23: (4, [(0, 6, 3), (4, 6, 5), (4, 4, 4)])
search 20: (-1, [(0, 6, 3), (4, 6, 5), (4, 4, 4)])
postfix result: 6
queue: [20, 30, 40, 50] front/rear/count: 1 1 4
BST after delete 40: [10, 20, 30, 50, 60, 70]
hash slots: [None, None, 9, 10, 17, 24, None]
BFS: A B C D E F ; F parent: C
DFS: A B D E F C

Exam and interview quick answers

1. Are two loops always quadratic? No. Read the bounds: sequential n-length loops do 2n work; this triangular nested loop does n(n+1)/2.
2. What must hold before binary search? The array is sorted, and low/high follow one consistent inclusive or half-open convention.
3. Which postfix operand is popped first? The right operand. Apply left operator right.
4. Can front equal rear when a queue is full? Yes in this count-based convention; count distinguishes full from empty.
5. Why remove the original inorder successor? Replacing the root key alone would leave a duplicate key.
6. Why use a tombstone in linear probing? Search must continue past a deleted slot to reach keys displaced by earlier collisions.
7. When does BFS give a shortest path? By edge count in an unweighted graph; unequal weights need a different rule.
8. Why state neighbor order for DFS? Several traversal orders can be valid. Alphabetical order makes this example reproducible.

A 30-minute revision plan

Spend 10 minutes tracing binary search and the circular queue, 10 minutes on postfix evaluation and BST deletion, then 10 minutes counting the loop and drawing BFS/DFS. Cover the answers before solving. Record the exact step where your trace differs instead of rereading the entire chapter.

For runnable C exercises, open the Data Structures Lab File. Use the Numericals Hub for other worked problems and the semester-wise Exam Notes hub to choose your next subject.

Sources and further reading

The examples, trace tables and revision plan are original. Concepts were checked against Programiz: binary search and OpenDSA's running-time analysis, queues, collision resolution and graph traversal, plus Open Data Structures: Binary Trees. See also hash-table deletion and Old Dominion University: expression evaluation.

Which trace gives you trouble: binary search, the queue wrap, or BST deletion? Put the step you got stuck on in the comments.