DSA LAB END TERM · EVEN SEM 2025-26
Master Every Topic,
Ace the Lab Exam.
Complete prep guide covering all 5 syllabus topics: Arrays, Strings, Linked List, Stack & Queue, and Trees — with Java code, dry-run traces, and quizzes.
✅Your Readiness Tracker
0/0 topics ready
TOPIC 01
EASY–MED
📦 Arrays
Traversal, Insertion, Deletion, Linear & Binary Search, Bubble & Selection Sort, Sliding Window.
TOPIC 02
EASY
🔤 Strings
String & character functions, traversal, palindrome, anagram, reverse, vowels.
TOPIC 03
MEDIUM
🔗 Linked List
Singly, Doubly, Circular LL — insert at beginning/end, delete first/last, count nodes.
TOPIC 04
MEDIUM
📚 Stack & Queue
Push/Pop/Peek, Infix→Postfix, Postfix eval, Enqueue/Dequeue, Circular Queue, Deque.
TOPIC 05
MEDIUM
🌳 Trees
Binary Tree, BST, Preorder/Inorder/Postorder, Height, Count Nodes, Same Tree.
PRACTICE
MCQ + CODE
🧠 Quiz
Topic-wise MCQs covering all 5 units. Instant feedback and explanations.
📌Exam Pattern Reminder
50 MCQs
Covers all 5 topics. Each question tests concept, code output, or complexity. Time budget: ~60 min.
2 Easy Coding Qs
Array/String/LL basics. Direct implementation. Time budget: ~20 min each.
1 Medium Coding Q
Stack application, Tree traversal, or Sliding Window. Time budget: ~20 min.
Language: Java
BYOD — bring your own device. Use Scanner for input. Always write Time & Space complexity.
📦Array Basics & Traversal
An array stores elements of the same type in contiguous memory. Index starts at 0.
Java — Declare, Input, Reverse
import java.util.Scanner; public class ArrayBasics { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; // Input for (int i = 0; i < n; i++) arr[i] = sc.nextInt(); // Reverse an Array int left = 0, right = n - 1; while (left < right) { int temp = arr[left]; arr[left++] = arr[right]; arr[right--] = temp; } // Print for (int x : arr) System.out.print(x + " "); } }
Check if Palindrome: Compare arr[i] with arr[n-1-i] for i from 0 to n/2. If all match → palindrome.
🔍Linear & Binary Search
Java — Linear Search
int linearSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) if (arr[i] == target) return i; return -1; // not found } // Time: O(n) | Space: O(1)
Java — Binary Search (sorted array)
int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; // safe mid if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } // Time: O(log n) | Space: O(1)
Binary Search Trace: arr=[1,3,5,7,9,11], target=7
step 1left=0, right=5, mid=2 → arr[2]=5 < 7 → left=3
step 2left=3, right=5, mid=4 → arr[4]=9 > 7 → right=3
step 3left=3, right=3, mid=3 → arr[3]=7 ✓ return 3
⚠️ Binary Search only works on sorted arrays! Always confirm sorted before applying.
🔃Bubble Sort & Selection Sort
Java — Bubble Sort
void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; // swap } } } } // Time: O(n²) | Space: O(1)
Java — Selection Sort
void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j; // swap arr[i] with arr[minIdx] int temp = arr[minIdx]; arr[minIdx] = arr[i]; arr[i] = temp; } } // Time: O(n²) | Space: O(1)
Key Difference:
Bubble Sort: compares adjacent elements, bubbles max to end each pass.
Selection Sort: finds minimum in unsorted part, places it at beginning.
Bubble Sort: compares adjacent elements, bubbles max to end each pass.
Selection Sort: finds minimum in unsorted part, places it at beginning.
👈👉Two Pointer Technique
Use two pointers from opposite ends or moving together to solve array problems in O(n).
Java — Two Sum II (sorted array)
int[] twoSum(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left < right) { int sum = arr[left] + arr[right]; if (sum == target) return new int[]{left, right}; else if (sum < target) left++; else right--; } return new int[]{-1, -1}; } // Time: O(n) | Space: O(1)
Java — Move Zeroes
void moveZeroes(int[] arr) { int j = 0; // pointer for next non-zero position for (int i = 0; i < arr.length; i++) if (arr[i] != 0) arr[j++] = arr[i]; while (j < arr.length) arr[j++] = 0; } // Time: O(n) | Space: O(1)
Java — Remove Duplicates from Sorted Array
int removeDuplicates(int[] arr) { if (arr.length == 0) return 0; int j = 1; for (int i = 1; i < arr.length; i++) if (arr[i] != arr[i - 1]) arr[j++] = arr[i]; return j; // new length } // Time: O(n) | Space: O(1)
🪟Sliding Window of Size K ⭐
Fix window size K. Slide it across the array. Track sum/max. Avoids O(n·k) brute force.
Java — Sum / Average / Max of Subarray Size K
void slidingWindow(int[] arr, int k) { int n = arr.length; if (n < k) { System.out.println("Invalid"); return; } int windowSum = 0; // Build first window for (int i = 0; i < k; i++) windowSum += arr[i]; int maxSum = windowSum; // Slide window for (int i = k; i < n; i++) { windowSum += arr[i] - arr[i - k]; // add new, remove old maxSum = Math.max(maxSum, windowSum); System.out.println("Window ["+(i-k+1)+","+i+"] Sum="+windowSum); } System.out.println("Max Sum = " + maxSum); } // Time: O(n) | Space: O(1)
Trace: arr=[2,1,5,1,3,2], k=3
initwindowSum = 2+1+5 = 8
i=3+arr[3]=1, -arr[0]=2 → sum=7 [1,5,1]
i=4+arr[4]=3, -arr[1]=1 → sum=9 [5,1,3] ✓MAX
i=5+arr[5]=2, -arr[2]=5 → sum=6 [1,3,2]
Max Sum = 9 ✓
📝All Practice Problems (Quick Reference)
10 Questions from Syllabus:
1. Reverse an Array — two pointer swap
2. Check if Array is Palindrome — compare left & right
3. Two Sum II (Sorted Array) — two pointers
4. Remove Duplicates from Sorted Array — two pointers
5. Move Zeroes — partition technique
6. Sum of Subarray of Size K — sliding window
7. Average of Subarray of Size K — sum / k each slide
8. Maximum Element in Subarray of Size K — track max
9. Count Subarrays of Size K — n - k + 1
10. Find All Anagrams in a String — frequency map + sliding window
1. Reverse an Array — two pointer swap
2. Check if Array is Palindrome — compare left & right
3. Two Sum II (Sorted Array) — two pointers
4. Remove Duplicates from Sorted Array — two pointers
5. Move Zeroes — partition technique
6. Sum of Subarray of Size K — sliding window
7. Average of Subarray of Size K — sum / k each slide
8. Maximum Element in Subarray of Size K — track max
9. Count Subarrays of Size K — n - k + 1
10. Find All Anagrams in a String — frequency map + sliding window
Java — Count Subarrays of Size K
// Number of subarrays of exactly size k = n - k + 1 int countSubarrays(int n, int k) { return n >= k ? n - k + 1 : 0; }
🔤String Basics in Java
Strings are immutable in Java. Use StringBuilder for efficient modification.
Java — Common String Methods
String s = "Hello World"; s.length(); // 11 s.charAt(0); // 'H' s.toUpperCase(); // "HELLO WORLD" s.toLowerCase(); // "hello world" s.substring(6); // "World" s.substring(0,5); // "Hello" s.trim(); // removes leading/trailing spaces s.replace('l','x'); // "Hexxo Worxd" s.contains("World");// true s.split(" "); // ["Hello","World"] s.toCharArray(); // char array // Character utility methods Character.isLetter('a'); // true Character.isDigit('3'); // true Character.isUpperCase('A'); // true Character.toLowerCase('A');// 'a'
🔁Reverse a String & Check Palindrome
Java — Reverse a String
String reverse(String s) { return new StringBuilder(s).reverse().toString(); } // Manual approach: String reverseManual(String s) { char[] ch = s.toCharArray(); int l = 0, r = ch.length - 1; while (l < r) { char temp = ch[l]; ch[l++] = ch[r]; ch[r--] = temp; } return new String(ch); }
Java — Check Palindrome String
boolean isPalindrome(String s) { int l = 0, r = s.length() - 1; while (l < r) { if (s.charAt(l++) != s.charAt(r--)) return false; } return true; }
🔡Count Vowels, Reverse Vowels, Count Occurrence
Java — Count Vowels & Consonants
void countVC(String s) { s = s.toLowerCase(); int vowels = 0, consonants = 0; for (char c : s.toCharArray()) { if ("aeiou".indexOf(c) >= 0) vowels++; else if (Character.isLetter(c)) consonants++; } System.out.println("Vowels: "+vowels+", Consonants: "+consonants); }
Java — Reverse Vowels of String
String reverseVowels(String s) { char[] ch = s.toCharArray(); int l = 0, r = ch.length - 1; String vowels = "aeiouAEIOU"; while (l < r) { while (l < r && vowels.indexOf(ch[l]) < 0) l++; while (l < r && vowels.indexOf(ch[r]) < 0) r--; char tmp = ch[l]; ch[l++] = ch[r]; ch[r--] = tmp; } return new String(ch); }
Java — Count Occurrence & Remove Spaces
int countOccurrence(String s, char target) { int count = 0; for (char c : s.toCharArray()) if (c == target) count++; return count; } String removeSpaces(String s) { return s.replace(" ", ""); // or: s.replaceAll("\\s+", "") }
📝Reverse Each Word of String
Java — Reverse Each Word
String reverseEachWord(String s) { String[] words = s.trim().split("\\s+"); StringBuilder sb = new StringBuilder(); for (String w : words) { sb.append(new StringBuilder(w).reverse()).append(' '); } return sb.toString().trim(); } // "hello world" → "olleh dlrow"
Example: Input: "I love Java" → Output: "I evol avaJ"
🔀Anagram Check (Find All Anagrams)
Two strings are anagrams if they have the same character frequencies.
Java — Check if Two Strings are Anagram
boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; int[] freq = new int[26]; for (int i = 0; i < s.length(); i++) { freq[s.charAt(i) - 'a']++; freq[t.charAt(i) - 'a']--; } for (int f : freq) if (f != 0) return false; return true; } // Time: O(n) | Space: O(1)
🔗Linked List Node Structure
Java — Node & LinkedList Class
class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } class LinkedList { Node head = null; // Traverse and print void display() { Node curr = head; while (curr != null) { System.out.print(curr.data + " → "); curr = curr.next; } System.out.println("null"); } }
3 Golden Rules:
1. Always check null before accessing .next or .data
2. Save the next pointer before modifying links
3. Draw the list on paper before writing code
1. Always check null before accessing .next or .data
2. Save the next pointer before modifying links
3. Draw the list on paper before writing code
➕Insert at Beginning & End
Java — Insert at Beginning
void insertAtBeginning(int data) { Node newNode = new Node(data); newNode.next = head; // point to old head head = newNode; // update head } // Time: O(1)
Java — Insert at End
void insertAtEnd(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; return; } Node curr = head; while (curr.next != null) curr = curr.next; curr.next = newNode; // link last node to new } // Time: O(n)
Insert 5 at Beginning: head→1→2→3→null
step 1newNode(5).next = head (1)
step 2head = newNode(5)
Result: head→5→1→2→3→null ✓
➖Delete First & Last Node
Java — Delete First Node
void deleteFirst() { if (head == null) { System.out.println("Empty list"); return; } head = head.next; // move head forward } // Time: O(1)
Java — Delete Last Node
void deleteLast() { if (head == null) return; if (head.next == null) { head = null; return; } // only 1 node Node curr = head; while (curr.next.next != null) curr = curr.next; curr.next = null; // disconnect last node } // Time: O(n)
🔢Count Number of Nodes
Java — Count Nodes
int countNodes() { int count = 0; Node curr = head; while (curr != null) { count++; curr = curr.next; } return count; } // Time: O(n) | Space: O(1)
✅ Complete SLL implementation — combine Node class + all 5 methods above for exam.
↔️Doubly Linked List
Each node has both next and prev pointers.
Java — Doubly Linked List Node & Insert
class DNode { int data; DNode next, prev; DNode(int data) { this.data = data; } } // Insert at beginning of DLL DNode insertFront(DNode head, int data) { DNode node = new DNode(data); node.next = head; if (head != null) head.prev = node; return node; // new head } // Delete a node in DLL void deleteNode(DNode node) { if (node.prev != null) node.prev.next = node.next; if (node.next != null) node.next.prev = node.prev; }
🔄Circular Linked List
Last node points back to head. No null at end.
Java — Circular LL Insert & Traverse
// Insert at end of Circular LL Node insertCircular(Node head, int data) { Node node = new Node(data); if (head == null) { node.next = node; return node; } Node curr = head; while (curr.next != head) curr = curr.next; curr.next = node; node.next = head; // circular link return head; } // Traverse Circular LL void displayCircular(Node head) { if (head == null) return; Node curr = head; do { System.out.print(curr.data + " → "); curr = curr.next; } while (curr != head); System.out.println("(back to head)"); }
⚠️ Always use
do-while loop for circular LL traversal to ensure head is visited!📚Stack — Array Based Implementation
LIFO: Last In, First Out. Top tracks the latest element.
Java — Stack using Array
class Stack { int[] arr; int top = -1; int capacity; Stack(int size) { arr = new int[size]; capacity = size; } void push(int val) { if (top == capacity - 1) { System.out.println("Stack Overflow"); return; } arr[++top] = val; } int pop() { if (top == -1) { System.out.println("Stack Underflow"); return -1; } return arr[top--]; } int peek() { if (top == -1) return -1; return arr[top]; } boolean isEmpty() { return top == -1; } boolean isFull() { return top == capacity - 1; } }
✅Valid Parentheses ⭐ (Most Important Stack Q)
Java — Valid Parentheses
boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (char c : s.toCharArray()) { if (c == '(' || c == '[' || c == '{') stack.push(c); else { if (stack.isEmpty()) return false; char top = stack.pop(); if (c == ')' && top != '(') return false; if (c == ']' && top != '[') return false; if (c == '}' && top != '{') return false; } } return stack.isEmpty(); // must be empty at end }
Trace: "({[]})"
'('push → stack: ['(']
'{'push → stack: ['(', '{']
'['push → stack: ['(', '{', '[']
']'pop '[' → match ✓ stack: ['(', '{']
'}'pop '{' → match ✓ stack: ['(']
')'pop '(' → match ✓ stack: []
Stack empty → return true ✓
📈Next Greater Element
For each element, find the first element to its right that is greater. Use monotonic stack.
Java — Next Greater Element
int[] nextGreater(int[] arr) { int n = arr.length; int[] result = new int[n]; Arrays.fill(result, -1); // default: no greater element Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { // Pop elements smaller than current while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) result[stack.pop()] = arr[i]; stack.push(i); } return result; } // Time: O(n) | Space: O(n)
Example: [4, 5, 2, 10, 8]
NGE: [5, 10, 10, -1, -1]
NGE: [5, 10, 10, -1, -1]
📐Infix to Postfix Conversion
Convert a+b*c → abc*+. Use operator precedence and stack.
Java — Infix to Postfix
int prec(char op) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; return 0; } String infixToPostfix(String exp) { StringBuilder result = new StringBuilder(); Stack<Character> stack = new Stack<>(); for (char c : exp.toCharArray()) { if (Character.isLetterOrDigit(c)) { result.append(c); } else if (c == '(') { stack.push(c); } else if (c == ')') { while (!stack.isEmpty() && stack.peek() != '(') result.append(stack.pop()); stack.pop(); // remove '(' } else { // operator while (!stack.isEmpty() && prec(stack.peek()) >= prec(c)) result.append(stack.pop()); stack.push(c); } } while (!stack.isEmpty()) result.append(stack.pop()); return result.toString(); } // "a+b*c" → "abc*+"
🚶Queue — Array Based (FIFO)
Java — Queue using Array
class Queue { int[] arr; int front = 0, rear = -1, size = 0, capacity; Queue(int cap) { arr = new int[cap]; capacity = cap; } void enqueue(int val) { if (size == capacity) { System.out.println("Queue Full"); return; } rear = (rear + 1) % capacity; arr[rear] = val; size++; } int dequeue() { if (size == 0) { System.out.println("Queue Empty"); return -1; } int val = arr[front]; front = (front + 1) % capacity; size--; return val; } boolean isEmpty() { return size == 0; } }
🔄Circular Queue & Deque
Circular Queue reuses empty spaces. The Queue above already uses circular indexing with (rear+1) % capacity.
Java — Deque (Double-Ended Queue)
// Java's built-in Deque — use in exams! Deque<Integer> dq = new ArrayDeque<>(); dq.addFirst(1); // add to front dq.addLast(2); // add to rear dq.removeFirst(); // remove from front dq.removeLast(); // remove from rear dq.peekFirst(); // view front without removing dq.peekLast(); // view rear without removing
Key Concept:
Circular Queue advantage: rear wraps around, reuses freed front slots → no wasted space.
Deque: can add/remove from both ends, O(1) per operation.
Circular Queue advantage: rear wraps around, reuses freed front slots → no wasted space.
Deque: can add/remove from both ends, O(1) per operation.
🌳Binary Tree — Node Structure
Java — Tree Node
class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; left = right = null; } } // Build a sample tree: // 1 // / \ // 2 3 // / \ // 4 5 TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5);
Key Terminology:
Root: topmost node | Leaf: node with no children | Height: longest path root→leaf
BST property: left < node < right (for all nodes)
Root: topmost node | Leaf: node with no children | Height: longest path root→leaf
BST property: left < node < right (for all nodes)
↩️Inorder Traversal (Left → Root → Right)
For a BST, inorder traversal gives elements in sorted order.
Java — Inorder (Recursive)
void inorder(TreeNode root) { if (root == null) return; // base case inorder(root.left); // visit left System.out.print(root.val + " "); // visit root inorder(root.right); // visit right }
Tree: 1(root), 2(left), 3(right), 4(ll), 5(lr)
callinorder(1) → go left
callinorder(2) → go left
callinorder(4) → null, print 4, null
backprint 2, go right → inorder(5) → print 5
backprint 1, go right → inorder(3) → print 3
Output: 4 2 5 1 3 ✓
➡️Preorder Traversal (Root → Left → Right)
Root is processed first. Used to copy/clone a tree.
Java — Preorder (Recursive)
void preorder(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); // visit root FIRST preorder(root.left); preorder(root.right); } // Same tree → Output: 1 2 4 5 3
Memory Hook: Pre = Root comes before children. "Root first, then explore."
⬅️Postorder Traversal (Left → Right → Root)
Root is processed last. Used to delete a tree or evaluate expression trees.
Java — Postorder (Recursive)
void postorder(TreeNode root) { if (root == null) return; postorder(root.left); postorder(root.right); System.out.print(root.val + " "); // visit root LAST } // Same tree → Output: 4 5 2 3 1
All Three Traversals Summary:
Tree: 1, left=2(children:4,5), right=3
Inorder: 4 2 5 1 3 | Preorder: 1 2 4 5 3 | Postorder: 4 5 2 3 1
Tree: 1, left=2(children:4,5), right=3
Inorder: 4 2 5 1 3 | Preorder: 1 2 4 5 3 | Postorder: 4 5 2 3 1
📏Height & Count Nodes
Java — Height of Binary Tree
int height(TreeNode root) { if (root == null) return 0; // base: null has height 0 int leftH = height(root.left); int rightH = height(root.right); return 1 + Math.max(leftH, rightH); } // Time: O(n)
Java — Count Total Nodes
int countNodes(TreeNode root) { if (root == null) return 0; return 1 + countNodes(root.left) + countNodes(root.right); } // Time: O(n) | Space: O(h) — h = height
Height Trace: same tree (root=1)
h(4)null,null → 1+max(0,0) = 1
h(5)null,null → 1
h(2)h(4)=1, h(5)=1 → 1+max(1,1) = 2
h(3)null,null → 1
h(1)h(2)=2, h(3)=1 → 1+max(2,1) = 3
Height = 3 ✓
🔁Same Tree & BST Basics
Java — Check if Two Trees are Same
boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; // both null if (p == null || q == null) return false; // one null if (p.val != q.val) return false; // values differ return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }
Java — BST Search & Insert
// BST Search boolean searchBST(TreeNode root, int key) { if (root == null) return false; if (root.val == key) return true; if (key < root.val) return searchBST(root.left, key); return searchBST(root.right, key); } // Time: O(h) — O(log n) for balanced BST // BST Insert TreeNode insertBST(TreeNode root, int val) { if (root == null) return new TreeNode(val); if (val < root.val) root.left = insertBST(root.left, val); else root.right = insertBST(root.right, val); return root; }
🧠MCQ Quiz — All Topics
Click an option. Get instant feedback. Reset to try again.
Score: 0 / 0 correct
📦 Arrays
Q1. What is the time complexity of Binary Search?
✅ Binary Search halves the search space each step → O(log n). It requires a sorted array.
📦 Arrays
Q2. Sliding window of size K over array of size N gives how many windows?
✅ Windows start at index 0, 1, 2, ..., N-K. That's N-K+1 windows total.
📦 Arrays
Q3. In Bubble Sort, after each outer loop pass, where does the largest element end up?
✅ Each pass "bubbles" the largest unsorted element to its final position at the end of the unsorted portion.
🔤 Strings
Q4. What does s.charAt(0) return for s = "Java"?
✅ charAt() returns a char primitive, not a String. 'J' is the first character.
🔤 Strings
Q5. Which method checks if two strings have the same character frequencies?
✅ equals() checks exact match. Anagram check: increment freq for s1 chars, decrement for s2 chars, all should be 0.
🔗 Linked List
Q6. Inserting at the beginning of a Singly Linked List takes:
✅ Just set newNode.next = head and head = newNode. No traversal needed. O(1).
🔗 Linked List
Q7. In a Circular Linked List, what does the last node's next point to?
✅ In a circular LL, the last node's next wraps back to head, forming a circle.
🔗 Linked List
Q8. A Doubly Linked List node has how many pointer fields?
✅ DLL nodes have both next (forward) and prev (backward) pointers, enabling bi-directional traversal.
📚 Stack & Queue
Q9. Stack follows which principle?
✅ Stack = LIFO. The last element pushed is the first to be popped. Like a stack of plates.
📚 Stack & Queue
Q10. For Valid Parentheses: input = "([)]". Output?
✅ "([)]" is invalid. Stack after '([': sees ')' — top is '[', mismatch! Returns false.
📚 Stack & Queue
Q11. Infix "a+b*c" in Postfix is:
✅ * has higher precedence than +. So b*c is evaluated first → bc*. Then a+result → abc*+.
🌳 Trees
Q12. For Inorder traversal, the order is:
✅ Inorder = Left → Root → Right. For a BST, this gives elements in sorted ascending order.
🌳 Trees
Q13. Height of a tree with only 1 node (root) is:
✅ By convention (as coded), a single node returns height 1. Null returns 0.
🌳 Trees
Q14. In a BST, where is the minimum value always found?
✅ BST property: all left subtree values < root. So the minimum is always at the leftmost node.
🌳 Trees
Q15. Postorder traversal is used for:
✅ Postorder processes children before root — perfect for deletion (free children before parent) and postfix expression evaluation.
📋Quick Reference Cheatsheet
All 5 topics at a glance — print this before entering the exam hall.
⏱ Time Complexities
Linear SearchO(n) / O(1)
Binary SearchO(log n) / O(1)
Bubble / Selection SortO(n²) / O(1)
Sliding Window (fixed K)O(n) / O(1)
LL Insert at HeadO(1)
LL Insert at TailO(n)
Stack Push/Pop/PeekO(1)
Queue Enqueue/DequeueO(1)
Tree TraversalsO(n) / O(h)
BST Search/InsertO(h) = O(log n)
🎯 Pattern Recognition
Fixed subarray/windowSliding Window
Sorted array searchBinary Search
Pair finding in sorted arrTwo Pointers
Brackets matchingStack
Next greater/smallerMonotonic Stack
Infix → PostfixStack + Precedence
BFS (level order)Queue
Tree recursionBase: null → return
BST sorted outputInorder traversal
Delete treePostorder traversal
🔗 Linked List Tricks
Insert at headO(1) — update head
Insert at tailO(n) — traverse to end
Delete headhead = head.next
Delete tailcurr.next.next == null
Count nodesLoop until null
Circular traversedo-while loop
DLL deleteUpdate prev & next
🌳 Tree Traversal Order
Inorder (L→N→R)BST → sorted
Preorder (N→L→R)Clone tree
Postorder (L→R→N)Delete tree
Base case alwaysif (root==null) return
Height formula1 + max(L, R)
Count formula1 + count(L) + count(R)
Same treeRecursive val check
📦 Array Quick Ops
Reverse arrayTwo pointer swap
Palindrome checkarr[i] == arr[n-1-i]
Max in window KSliding + track max
Move zeroesPartition pointer j
Remove duplicatesTwo pointer j
Two Sum (sorted)left++, right--
🏁 Exam Day Tips
Always check nullBefore .next or .data
Write base cases firstTree recursion key
Dry run on paperBefore typing code
State complexity// Time: O(?) Space: O(?)
Use ScannerRead input properly
Edge: empty inputn=0, null, empty string
📌Important Notes from Syllabus
Focus on traversal order
Memorize In/Pre/Post order. Know which gives sorted output (Inorder in BST).
Dry run before coding
Always trace through an example manually before writing any code.
Practice recursion base case
Every recursive tree function starts with: if (root == null) return 0/false/null.
Understand node visiting sequence
Draw the tree and number each step of the traversal on paper.