Skip to content
CampusPrep
CS-402 · Analysis Design of Algorithm/Quick Revision Short Notes

Analysis Design of Algorithm (CS-402) - Unit 5 Short Notes

How unit 5 is examined

This unit covers search trees (BST, AVL, 2-3, B-trees), tree and graph traversal, and NP-completeness; the marks sit in AVL insertion, B-tree construction, OBST tables, traversals, DFS versus BFS, and P versus NP.

Binary search trees

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A binary search tree (BST) is a binary tree in which, for every node, all keys in the left subtree are smaller and all keys in the right subtree are larger than the node's key.</mark>

Key points.

  1. Search compares the key with the root and moves left or right, so it follows one root-to-leaf path and costs $O(h)$ for height $h$.
  2. Insertion searches for the key and attaches the new node as a leaf at the point where the search falls off the tree.
  3. Inorder traversal of a BST visits the keys in sorted order, which is the standard test for a valid BST.
  4. Deletion has three cases: a leaf is simply removed, a node with one child is replaced by that child, and a node with two children is replaced by its inorder successor (or predecessor), which is then deleted from its old place.
  5. Height is $O(\log n)$ on average for random insertions but $O(n)$ for sorted insertions, when the tree degenerates into a chain; this is why balanced trees exist.
  6. An optimal BST (OBST) is the BST of minimum expected search cost for given access probabilities, found by dynamic programming.

Deletion algorithm.

Step 1: Search for x from the root t; if not found, report "not found" and stop.
Step 2: If x is a leaf, delete it (parent pointer becomes NULL).
Step 3: If x has one child, link x's parent directly to that child.
Step 4: If x has two children, find s = smallest key in x's right subtree.
Step 5: Copy s into x's node, then delete s from the right subtree (s has no left child, so Step 2 or 3 applies).

Time is $O(h)$: $O(\log n)$ on average and $O(n)$ in the worst case.

Optimal BST formulas. With successful weights $p_j$ and unsuccessful weights $q_j$:

$$w(i,i)=q_i,\quad w(i,j)=w(i,j-1)+p_j+q_j$$ $$c(i,i)=0,\quad c(i,j)=w(i,j)+\min_{i<k\le j}\{c(i,k-1)+c(k,j)\},\quad r(i,j)=\text{the }k\text{ that gives the minimum}$$

Example. Identifiers (double, int, for, if), $p=(3,3,1,1)$, $q=(2,3,1,1,1)$ (five $q$ values are needed for $q_0..q_4$; the printed paper lists four, so $q_4=1$ is assumed). Initial $w(i,i)=q_i=2,3,1,1,1$ and $c(i,i)=0$.

$(i,j)$ 01 12 23 34 02 13 24 03 14 04
$w$ 8 7 3 3 12 9 5 14 11 16
$c$ 8 7 3 3 19 12 8 25 19 32
$r$ 1 2 3 4 1 2 3 2 2 2

Check: $c(0,2)=12+\min(c(0,0)+c(1,2),\,c(0,1)+c(2,2))=12+\min(7,8)=19$ with $k=1$. Root $r(0,4)=2$ (int); left is $r(0,1)=1$ (double); right is $r(2,4)=3$ (for), whose right child is $r(3,4)=4$ (if).

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-01" viewBox="0 0 360 198" width="360" height="198" role="img" aria-label="Optimal BST from r(i,j): root int, cost c(0,4) = 32"><style>#dsfig-u5-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-01 .t{fill:#16181D;font-weight:500}#dsfig-u5-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-01 .dot{fill:#16181D}#dsfig-u5-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-01 .ah{fill:#454C5A}#dsfig-u5-01 .ah.hi{fill:#2340B8}#dsfig-u5-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-01 .e{stroke:#B1B7C3}html.dark #dsfig-u5-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-01 .t{fill:#E6E8ED}html.dark #dsfig-u5-01 .t.inv{fill:#0F1115}html.dark #dsfig-u5-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-01 .dot{fill:#E6E8ED}html.dark #dsfig-u5-01 .ann{fill:#8FA3FF}html.dark #dsfig-u5-01 .lbl{fill:#858D9C}html.dark #dsfig-u5-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-01 .ah{fill:#B1B7C3}html.dark #dsfig-u5-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah13" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh13" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="129.5" y1="39" x2="52.5" y2="103"/><line class="e" x1="129.5" y1="39" x2="206.5" y2="103"/><line class="e" x1="206.5" y1="103" x2="283.5" y2="167"/><circle class="n" cx="129.5" cy="39" r="17"/><text class="t" x="129.5" y="39" dy=".35em" text-anchor="middle">int</text><rect class="n" x="19" y="88" width="67" height="30" rx="8"/><text class="t" x="52.5" y="103" dy=".35em" text-anchor="middle">double</text><circle class="n" cx="206.5" cy="103" r="17"/><text class="t" x="206.5" y="103" dy=".35em" text-anchor="middle">for</text><circle class="n" cx="283.5" cy="167" r="17"/><text class="t" x="283.5" y="167" dy=".35em" text-anchor="middle">if</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Optimal BST from r(i,j): root int, cost c(0,4) = 32</figcaption></figure> Answer frame. Open with the BST definition; for deletion write the three cases in order and end with $O(h)$; for the OBST numerical write the two formulas, fill the three tables diagonal by diagonal, then draw the tree from $r(0,4)$ downwards and close with cost 32.

Pitfall: Deleting a two-child node by simply removing it breaks the tree; always replace it with the inorder successor or predecessor.

Asked: [14 marks] (Jun 2020) Write short notes: BST, tree traversals, NP-completeness, reliability design Asked: [7 marks] (Dec 2024) Use OBST to compute $w(i,j)$, $r(i,j)$, $c(i,j)$ for (double, int, for, if), $p=(3,3,1,1)$, $q=(2,3,1,1)$; construct the optimal BST Asked: [7 marks] (Jun 2025) Write an algorithm to delete element $x$ from BST $t$; give its time complexity

Height balanced trees

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. ==An AVL (height-balanced) tree is a BST in which, for every node, the heights of the left and right subtrees differ by at most one, that is, the balance factor $BF=h_L-h_R\in\{-1,0,1\}$.==

Key points.

  1. An AVL tree is better than a plain BST because its height is always $O(\log n)$ (at most about $1.44\log_2 n$), so search, insert and delete stay $O(\log n)$, while a BST fed sorted keys becomes a chain with $O(n)$ operations.
  2. After every insertion the balance factors on the path back to the root are updated, and the first (lowest) node with $|BF|=2$ is repaired.
  3. LL case: the new key went into the left subtree of the left child, fixed by one right rotation at the unbalanced node.
  4. RR case: the key went into the right subtree of the right child, fixed by one left rotation.
  5. LR case: the key went into the right subtree of the left child, fixed by a left rotation on the child and then a right rotation on the node (double rotation).
  6. RL case: the key went into the left subtree of the right child, fixed by a right rotation on the child and then a left rotation on the node.
  7. One rotation (single or double) restores the height the subtree had before the insertion, so at most one rebalancing is needed per insertion; rotations preserve the inorder order.

Example. Insert 342, 206, 444, 523, 607, 301, 142, 183, 102, 157, 149.

Insert Imbalance Fix Tree after (root first)
342, 206, 444, 523 none none 342(206,444(,523))
607 444 (RR) left rotation at 444 342(206,523(444,607))
301, 142, 183, 102 none none 342(206(142(102,183),301),523(444,607))
157 206 (LR) rotate 142 left, then 206 right 342(183(142(102,157),206(,301)),523(444,607))
149 342 (LL) right rotation at 342 final tree below

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-02" viewBox="0 0 536 262" width="536" height="262" role="img" aria-label="Final AVL tree after all 11 insertions, root 183, height 4"><style>#dsfig-u5-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-02 .t{fill:#16181D;font-weight:500}#dsfig-u5-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-02 .dot{fill:#16181D}#dsfig-u5-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-02 .ah{fill:#454C5A}#dsfig-u5-02 .ah.hi{fill:#2340B8}#dsfig-u5-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-02 .e{stroke:#B1B7C3}html.dark #dsfig-u5-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-02 .t{fill:#E6E8ED}html.dark #dsfig-u5-02 .t.inv{fill:#0F1115}html.dark #dsfig-u5-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-02 .dot{fill:#E6E8ED}html.dark #dsfig-u5-02 .ann{fill:#8FA3FF}html.dark #dsfig-u5-02 .lbl{fill:#858D9C}html.dark #dsfig-u5-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-02 .ah{fill:#B1B7C3}html.dark #dsfig-u5-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah14" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh14" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="212" y1="39" x2="80" y2="103"/><line class="e" x1="212" y1="39" x2="344" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="168" y2="167"/><line class="e" x1="168" y1="167" x2="124" y2="231"/><line class="e" x1="344" y1="103" x2="256" y2="167"/><line class="e" x1="344" y1="103" x2="432" y2="167"/><line class="e" x1="256" y1="167" x2="300" y2="231"/><line class="e" x1="432" y1="167" x2="388" y2="231"/><line class="e" x1="432" y1="167" x2="476" y2="231"/><circle class="n" cx="212" cy="39" r="17"/><text class="t" x="212" y="39" dy=".35em" text-anchor="middle">183</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">142</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">102</text><circle class="n" cx="168" cy="167" r="17"/><text class="t" x="168" y="167" dy=".35em" text-anchor="middle">157</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">149</text><circle class="n" cx="344" cy="103" r="17"/><text class="t" x="344" y="103" dy=".35em" text-anchor="middle">342</text><circle class="n" cx="256" cy="167" r="17"/><text class="t" x="256" y="167" dy=".35em" text-anchor="middle">206</text><circle class="n" cx="300" cy="231" r="17"/><text class="t" x="300" y="231" dy=".35em" text-anchor="middle">301</text><circle class="n" cx="432" cy="167" r="17"/><text class="t" x="432" y="167" dy=".35em" text-anchor="middle">523</text><circle class="n" cx="388" cy="231" r="17"/><text class="t" x="388" y="231" dy=".35em" text-anchor="middle">444</text><circle class="n" cx="476" cy="231" r="17"/><text class="t" x="476" y="231" dy=".35em" text-anchor="middle">607</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Final AVL tree after all 11 insertions, root 183, height 4</figcaption></figure> Answer frame. Open with the AVL condition $|h_L-h_R|\le1$; draw one imbalance with balance factors and its rotation for the "explain" question; develop points 1, 2, then the four rotation cases; for the numerical, show the table of rotations and the final tree, then close with $O(\log n)$ height.

Asked: [7 marks] (Nov 2019, Dec 2020) In what way is an AVL tree better than a binary tree? Insert 342, 206, 444, 523, 607, 301, 142, 183, 102, 157, 149 into an AVL tree Asked: [7 marks] (Dec 2024, Jun 2025) Explain in detail height balanced tree with an example; what is balance factor in an AVL tree, and give an example to balance it

2-3 trees

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A 2-3 tree is a search tree in which every internal node is a 2-node (one key, two children) or a 3-node (two keys, three children), and all leaves are at the same level.</mark>

Key points.

  1. In a 3-node with keys $a<b$, the three subtrees hold keys less than $a$, between $a$ and $b$, and greater than $b$.
  2. Search works like BST search, choosing one of two or three branches at each node.
  3. Insertion goes to a leaf; if the leaf becomes a 3-key node it splits, the middle key moves up to the parent, and splits may repeat up to the root, which is the only way the height grows.
  4. Because the tree grows at the root, it stays perfectly balanced, so height is $O(\log n)$ and search, insert and delete cost $O(\log n)$.
  5. Uses: keeping sorted data with guaranteed balance, dictionaries and indexes; it is the idea behind B-trees.
  6. Better than BST because a BST can degenerate to $O(n)$ on skewed insertions, while a 2-3 tree cannot.
  7. Limitations: implementation is more complex (two node types, splitting and merging), constant factors are higher, and the node overhead makes it slower than other balanced trees in practice.

Diagram. Insert 10, 20, 30, 40, 50: 10, 20 fill one node; 30 splits it (20 rises); 40 joins leaf 30; 50 splits [30 40 50], 40 rises. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-03" viewBox="0 0 186 134" width="186" height="134" role="img" aria-label="2-3 tree after inserting 10, 20, 30, 40, 50 (one 3-node root, three leaves)"><style>#dsfig-u5-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-03 .t{fill:#16181D;font-weight:500}#dsfig-u5-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-03 .dot{fill:#16181D}#dsfig-u5-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-03 .ah{fill:#454C5A}#dsfig-u5-03 .ah.hi{fill:#2340B8}#dsfig-u5-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-03 .e{stroke:#B1B7C3}html.dark #dsfig-u5-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-03 .t{fill:#E6E8ED}html.dark #dsfig-u5-03 .t.inv{fill:#0F1115}html.dark #dsfig-u5-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-03 .dot{fill:#E6E8ED}html.dark #dsfig-u5-03 .ann{fill:#8FA3FF}html.dark #dsfig-u5-03 .lbl{fill:#858D9C}html.dark #dsfig-u5-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-03 .ah{fill:#B1B7C3}html.dark #dsfig-u5-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah15" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh15" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="51" y1="54" x2="31" y2="103"/><line class="e" x1="81" y1="54" x2="81" y2="103"/><line class="e" x1="111" y1="54" x2="131" y2="103"/><rect class="n" x="51" y="24" width="60" height="30" rx="3"/><text class="t" x="66" y="39" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="81" y1="24" x2="81" y2="54"/><text class="t" x="96" y="39" dy=".35em" text-anchor="middle">40</text><circle class="n" cx="31" cy="103" r="17"/><text class="t" x="31" y="103" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="81" cy="103" r="17"/><text class="t" x="81" y="103" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="131" cy="103" r="17"/><text class="t" x="131" y="103" dy=".35em" text-anchor="middle">50</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">2-3 tree after inserting 10, 20, 30, 40, 50 (one 3-node root, three leaves)</figcaption></figure> Answer frame. Open with the 2-node/3-node definition; draw the tree above; develop points 1-4 with the insertion example; for the "used for / better / limitations" question use points 5, 6, 7 in that order; close with $O(\log n)$.

Asked: [7 marks] (Jun 2023) What are 2-3 trees used for? Why are they better than BST? Write the limitations of 2-3 trees in CSE Asked: [7 marks] (Jun 2024) Explain in detail about 2-3 trees with an example

B-trees

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A B-tree of order $m$ is a balanced multiway search tree in which every node has at most $m$ children and $m-1$ keys, every non-root internal node has at least $\lceil m/2\rceil$ children, and all leaves are at the same level.</mark>

Key points.

  1. A node with $k$ keys has $k+1$ children, and keys inside a node are sorted, so it works as a multiway search node.
  2. The root has at least 2 children (unless it is a leaf); every other node holds at least $\lceil m/2\rceil-1$ keys and at most $m-1$.
  3. All leaves lie at the same depth, so the tree is perfectly height-balanced.
  4. Need: each node is sized to one disk block, so a very large database or file index is searched with few disk reads, because the high fanout makes the tree shallow.
  5. Insertion goes into a leaf; on overflow the node splits around its median key, the median moves up, and the root splits last, growing the tree by one level.
  6. Deletion removes the key and, on underflow, borrows from a sibling or merges with it.
  7. Height for $n$ keys and minimum degree $t=\lceil m/2\rceil$: $h\le\log_t\frac{n+1}{2}$, that is $O(\log n)$; operations cost $O(\log n)$ node visits.

Example. Order 5 (max 4 keys, min 2) for 2, 8, 5, 6, 13, 9, 14, 12, 19, 24, 18, 15, 5, 16, 20, 21 (the repeated 5 is ignored).

Step Result
2, 8, 5, 6 one leaf [2 5 6 8]
13 overflow [2 5 6 8 13], median 6 rises: [6]([2 5],[8 13])
9, 14 [8 9 13 14]
12 overflow [8 9 12 13 14], 12 rises: [6 12]([2 5],[8 9],[13 14])
19, 24 [13 14 19 24]
18 overflow [13 14 18 19 24], 18 rises: [6 12 18], leaves [2 5],[8 9],[13 14],[19 24]
15, 16, 20, 21 fill leaves; no more splits

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-04" viewBox="0 0 460 130" width="460" height="130" role="img" aria-label="Final B-tree of order 5, all leaves at level 2"><style>#dsfig-u5-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-04 .t{fill:#16181D;font-weight:500}#dsfig-u5-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-04 .dot{fill:#16181D}#dsfig-u5-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-04 .ah{fill:#454C5A}#dsfig-u5-04 .ah.hi{fill:#2340B8}#dsfig-u5-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-04 .e{stroke:#B1B7C3}html.dark #dsfig-u5-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-04 .t{fill:#E6E8ED}html.dark #dsfig-u5-04 .t.inv{fill:#0F1115}html.dark #dsfig-u5-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-04 .dot{fill:#E6E8ED}html.dark #dsfig-u5-04 .ann{fill:#8FA3FF}html.dark #dsfig-u5-04 .lbl{fill:#858D9C}html.dark #dsfig-u5-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-04 .ah{fill:#B1B7C3}html.dark #dsfig-u5-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah16" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh16" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="158" y1="52" x2="44" y2="101"/><line class="e" x1="188" y1="52" x2="120" y2="101"/><line class="e" x1="218" y1="52" x2="226" y2="101"/><line class="e" x1="248" y1="52" x2="362" y2="101"/><rect class="n" x="158" y="22" width="90" height="30" rx="3"/><text class="t" x="173" y="37" dy=".35em" text-anchor="middle">6</text><line class="kd" x1="188" y1="22" x2="188" y2="52"/><text class="t" x="203" y="37" dy=".35em" text-anchor="middle">12</text><line class="kd" x1="218" y1="22" x2="218" y2="52"/><text class="t" x="233" y="37" dy=".35em" text-anchor="middle">18</text><rect class="n" x="14" y="86" width="60" height="30" rx="3"/><text class="t" x="29" y="101" dy=".35em" text-anchor="middle">2</text><line class="kd" x1="44" y1="86" x2="44" y2="116"/><text class="t" x="59" y="101" dy=".35em" text-anchor="middle">5</text><rect class="n" x="90" y="86" width="60" height="30" rx="3"/><text class="t" x="105" y="101" dy=".35em" text-anchor="middle">8</text><line class="kd" x1="120" y1="86" x2="120" y2="116"/><text class="t" x="135" y="101" dy=".35em" text-anchor="middle">9</text><rect class="n" x="166" y="86" width="120" height="30" rx="3"/><text class="t" x="181" y="101" dy=".35em" text-anchor="middle">13</text><line class="kd" x1="196" y1="86" x2="196" y2="116"/><text class="t" x="211" y="101" dy=".35em" text-anchor="middle">14</text><line class="kd" x1="226" y1="86" x2="226" y2="116"/><text class="t" x="241" y="101" dy=".35em" text-anchor="middle">15</text><line class="kd" x1="256" y1="86" x2="256" y2="116"/><text class="t" x="271" y="101" dy=".35em" text-anchor="middle">16</text><rect class="n" x="302" y="86" width="120" height="30" rx="3"/><text class="t" x="317" y="101" dy=".35em" text-anchor="middle">19</text><line class="kd" x1="332" y1="86" x2="332" y2="116"/><text class="t" x="347" y="101" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="362" y1="86" x2="362" y2="116"/><text class="t" x="377" y="101" dy=".35em" text-anchor="middle">21</text><line class="kd" x1="392" y1="86" x2="392" y2="116"/><text class="t" x="407" y="101" dy=".35em" text-anchor="middle">24</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Final B-tree of order 5, all leaves at level 2</figcaption></figure> Answer frame. Open with the order-$m$ definition; list properties (points 1-3), then the need (point 4) and the height formula; for the construction question state max 4 and min 2 keys, show each split, draw the final tree and add "all leaves at the same level"; close with $O(\log n)$ disk accesses.

Asked: [7 marks] (May 2019, Jun 2020, Dec 2020) What are B-trees? Write its properties; what is the need for B-trees; height of a B-tree of order $m$; how are they created; advantages Asked: [7 marks] (Jun 2022) Construct a B-tree of order 5 for 2, 8, 5, 6, 13, 9, 14, 12, 19, 24, 18, 15, 5, 16, 20, 21 Asked: [14 marks] (Nov 2019, Jun 2025) Short notes (any two): B-tree, subset sum problem, Big-Oh notation Asked: [14 marks] (Jun 2025) Short notes (any two): B-trees, tree traversal, reliability design

Basic search and traversal techniques for trees and graphs

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A traversal visits every node of a tree or graph exactly once in a systematic order: inorder, preorder and postorder for binary trees, and depth-first search (DFS) and breadth-first search (BFS) for graphs.</mark>

Key points.

  1. Preorder is root, left, right; inorder is left, root, right; postorder is left, right, root, and each is a recursive $O(n)$ procedure.
  2. Inorder of a BST gives sorted keys; preorder is used to copy a tree; postorder is used to delete a tree or evaluate expressions.
  3. DFS goes as deep as possible along a path before backtracking, using recursion or a stack.
  4. BFS visits vertices level by level from the source, using a queue.
  5. Both cost $O(V+E)$ with adjacency lists and $O(V^2)$ with a matrix.
  6. DFS gives topological sort, cycle detection and connected components; BFS gives shortest paths in unweighted graphs.

Example (tree). Root A; B(D,E(I,)); C(F,G(,J)).

Traversal Order
Preorder A B D E I C F G J
Inorder D B I E A F C G J
Postorder D I E B F J G C A

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-05" viewBox="0 0 448 262" width="448" height="262" role="img" aria-label="Binary tree used for the traversals"><style>#dsfig-u5-05 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-05 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-05 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-05 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-05 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-05 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-05 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-05 .t{fill:#16181D;font-weight:500}#dsfig-u5-05 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-05 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-05 .dot{fill:#16181D}#dsfig-u5-05 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-05 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-05 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-05 .ah{fill:#454C5A}#dsfig-u5-05 .ah.hi{fill:#2340B8}#dsfig-u5-05 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-05 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-05 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-05 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-05 .e{stroke:#B1B7C3}html.dark #dsfig-u5-05 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-05 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-05 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-05 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-05 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-05 .t{fill:#E6E8ED}html.dark #dsfig-u5-05 .t.inv{fill:#0F1115}html.dark #dsfig-u5-05 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-05 .dot{fill:#E6E8ED}html.dark #dsfig-u5-05 .ann{fill:#8FA3FF}html.dark #dsfig-u5-05 .lbl{fill:#858D9C}html.dark #dsfig-u5-05 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-05 .ah{fill:#B1B7C3}html.dark #dsfig-u5-05 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-05 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-05 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-05 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah17" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh17" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="212" y1="39" x2="80" y2="103"/><line class="e" x1="212" y1="39" x2="300" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="168" y2="167"/><line class="e" x1="168" y1="167" x2="124" y2="231"/><line class="e" x1="300" y1="103" x2="256" y2="167"/><line class="e" x1="300" y1="103" x2="344" y2="167"/><line class="e" x1="344" y1="167" x2="388" y2="231"/><circle class="n" cx="212" cy="39" r="17"/><text class="t" x="212" y="39" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="168" cy="167" r="17"/><text class="t" x="168" y="167" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">I</text><circle class="n" cx="300" cy="103" r="17"/><text class="t" x="300" y="103" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="256" cy="167" r="17"/><text class="t" x="256" y="167" dy=".35em" text-anchor="middle">F</text><circle class="n" cx="344" cy="167" r="17"/><text class="t" x="344" y="167" dy=".35em" text-anchor="middle">G</text><circle class="n" cx="388" cy="231" r="17"/><text class="t" x="388" y="231" dy=".35em" text-anchor="middle">J</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Binary tree used for the traversals</figcaption></figure>

Construct a tree from inorder $I$ and postorder $P$. The last element of $P$ is the root; find it in $I$; elements to its left form the left subtree and to its right the right subtree. Build the right subtree first, because postorder is left, right, root and we read $P$ backwards.

def build(I, P):
    pos = {v: i for i, v in enumerate(I)}   # hashmap: O(1) root lookup
    k = [len(P) - 1]
    def f(lo, hi):
        if lo > hi: return None
        v = P[k[0]]; k[0] -= 1; m = pos[v]
        r = f(m + 1, hi)                    # right first
        l = f(lo, m - 1)
        return (v, l, r)
    return f(0, len(I) - 1)

Complexity: searching $I$ linearly for each root gives $T(n)=T(k)+T(n-k-1)+O(n)$, which is $O(n^2)$ for a skewed tree and $O(n\log n)$ for a balanced one; the hashmap makes it $O(n)$.

DFS versus BFS (graph: edges A-B, A-C, B-D, C-D, D-E, start A, neighbours in alphabetical order). DFS order is A B D C E; BFS order is A B C D E.

Point DFS BFS
Data structure Stack or recursion Queue
Order Deep first, then backtrack Level by level
Time $O(V+E)$ $O(V+E)$
Space $O(h)$, depth of path $O(w)$, widest level
Shortest path Not guaranteed Yes, unweighted
Uses Topological sort, cycles, components Shortest hops, level order

Depth versus queue example. The path graph $P_n$ ($v_1-v_2-\dots-v_n$) started at end vertex $V=v_1$: DFS recurses $v_1\to v_2\to\dots\to v_n$, a depth of $n-1$, while BFS holds only the one newly found neighbour in the queue at any time.

DFS reaches every reachable vertex (proof). Suppose some vertex reachable from $V$ is not visited; take a path from $V$ to it and let $u$ be the first unvisited vertex on it, with predecessor $w$ visited. When DFS visited $w$ it examined every neighbour of $w$, and $u$ was unvisited, so it would have been visited then, a contradiction. Hence all reachable vertices are visited (induction on the path length from $V$).

Answer frame. For traversals write the three rules, draw the tree, then list the three sequences; for DFS versus BFS define both, run both on one graph, then give the table; for the proof use the "first unvisited vertex" argument and end with "hence all reachable vertices are visited".

Asked: [7 marks] (Jun 2020, Jun 2022, Jun 2023) Differentiate between DFS and BFS by an example Asked: [7 marks] (Nov 2019, Jun 2022) Show preorder, inorder and postorder for the following tree Asked: [7 marks] (Nov 2023) Write a function to construct a binary tree from inorder $I$ and postorder $P$; what is its complexity? Asked: [7 marks] (Nov 2023) Give an n-vertex graph where DFS recursion depth from $V$ is $n-1$ but the BFS queue holds at most one vertex at a time Asked: [7 marks] (Jun 2025) Show that DFS visits all vertices in $G$ reachable from $V$

NP-completeness

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A problem is NP-complete if it is in NP and every problem in NP can be reduced to it in polynomial time; so if one NP-complete problem is solved in polynomial time, all of NP is.</mark>

Key points.

  1. Class P holds decision problems solvable by a deterministic algorithm in polynomial time, such as sorting and shortest path.
  2. Class NP holds decision problems solvable in polynomial time by a nondeterministic algorithm, equivalently problems whose proposed solution can be verified in polynomial time, such as SAT and Hamiltonian cycle.
  3. Every problem in P is also in NP, so $P\subseteq NP$; whether $P=NP$ is the open question.
  4. Problem $A$ reduces to $B$ ($A\le_p B$) if a polynomial-time transformation turns instances of $A$ into instances of $B$ with the same answer.
  5. NP-hard means at least as hard as every problem in NP (need not be in NP); NP-complete means NP-hard and in NP.
  6. Cook's theorem proves that SAT is NP-complete, giving the first NP-complete problem; others follow by reduction from it (SAT, 3-SAT, clique, vertex cover, Hamiltonian cycle, TSP, graph colouring, subset sum).
  7. Nondeterministic algorithms use Choice() (guess), Failure() and Success(); they are checked in polynomial time.
Point P NP
Meaning Solvable in polynomial time Verifiable in polynomial time
Machine Deterministic Nondeterministic
Example Sorting, shortest path SAT, Hamiltonian cycle, TSP
Relation $P\subseteq NP$ Contains P and NP-complete
Status Efficient $P=NP$ unresolved

Nondeterministic subset sum, $O(n)$.

Step 1: for i = 1 to n: x[i] = Choice(0,1)   // guess whether a[i] is picked
Step 2: sum = sum over i of a[i]*x[i]         // O(n)
Step 3: if sum == m then Success() else Failure()

The guess and the sum each take $O(n)$ steps, so the algorithm is $O(n)$ nondeterministically.

Hamiltonian cycle is a cycle through every vertex exactly once; graph colouring assigns colours so adjacent vertices differ, the least number being the chromatic number; both are NP-complete.

Vertex cover approximation. A vertex cover is a set of vertices touching every edge; finding a minimum one is NP-hard.

Step 1: C = empty set, E' = all edges
Step 2: pick any edge (u,v) in E'; add u and v to C
Step 3: remove from E' every edge touching u or v
Step 4: repeat Steps 2-3 until E' is empty; return C

Runtime is $O(V+E)$. The chosen edges form a matching, and any cover must contain at least one endpoint of each, so $OPT\ge|M|$ while $|C|=2|M|$; hence $|C|\le2\cdot OPT$ (ratio 2). Example: path a-b-c-d picks (a,b) and (c,d), giving $C=\{a,b,c,d\}$ against optimum $\{b,c\}$.

Answer frame. Open with P, NP and reduction definitions; develop points 1-6 with SAT and TSP as examples and Cook's theorem; for "difference" use the table; close with the open $P=NP$ question.

Pitfall: NP does not mean "not polynomial"; it means nondeterministic polynomial, and P is inside NP.

Asked: [14 marks] (May 2019, Dec 2020) Short notes: NP-completeness, tree traversals, Hamiltonian cycle, graph colouring Asked: [7 marks] (Jun 2022) Discuss in detail NP-complete problems with example Asked: [7 marks] (Jun 2025) Obtain a nondeterministic $O(n)$ algorithm to decide whether a subset of $n$ numbers sums to $m$ Asked: [7 marks] (Jun 2026) Explain the difference between P and NP Asked: [7 marks] (Jun 2026) Explain approximation algorithms for Vertex Cover

Last-minute revision

  • BST: left smaller, right larger; inorder gives sorted order; search, insert and delete cost $O(h)$.
  • BST deletion has three cases: leaf, one child, two children (use inorder successor).
  • OBST: $w(i,j)=w(i,j-1)+p_j+q_j$; $c(i,j)=w(i,j)+\min_k[c(i,k-1)+c(k,j)]$; the paper's result is $c(0,4)=32$, root int.
  • AVL: $BF=h_L-h_R\in\{-1,0,1\}$; four cases LL, RR, LR, RL; height $O(\log n)$.
  • AVL sequence 342...149 uses RR at 444, LR at 206, LL at 342; final root 183.
  • 2-3 tree: 2-nodes and 3-nodes, all leaves at one level, splits push the middle key up.
  • B-tree order $m$: at most $m-1$ keys, at least $\lceil m/2\rceil$ children; order 5 means 2 to 4 keys.
  • B-tree order 5 answer: root [6 12 18], four leaves.
  • Preorder A B D E I C F G J; inorder D B I E A F C G J; postorder D I E B F J G C A.
  • DFS uses a stack, BFS a queue; both $O(V+E)$; the path graph gives DFS depth $n-1$ with BFS queue size 1.
  • $P\subseteq NP$; NP-complete = NP-hard and in NP; Cook's theorem: SAT is NP-complete.
  • Vertex cover matching algorithm has ratio 2.

Memory hooks

  • AVL cases: the letters name the path from the unbalanced node (LR = left child, then its right side), and LR/RL need two rotations.
  • B-tree: "big node, short tree" - one node per disk block.
  • Preorder "root first", postorder "root last", inorder "root in the middle".
  • DFS = Deep Follow Stack; BFS = Break into Floors with a Queue.
  • NP = "Nondeterministic Polynomial", not "Not Polynomial".

Coverage checklist

  • Binary search trees: BST definition, deletion, OBST tables and tree; short notes (Jun 2020), OBST (Dec 2024), delete (Jun 2025).
  • height balanced trees: AVL definition, balance factor, rotations, 11-key insertion; Nov 2019, Dec 2020, Dec 2024, Jun 2025.
  • 2-3 trees: properties, insertion, uses and limitations; Jun 2023, Jun 2024.
  • B-trees: definition, properties, need, height, order-5 construction, short notes; May 2019, Nov 2019, Jun 2020, Dec 2020, Jun 2022, Jun 2025.
  • basic search and traversal techniques for trees and graphs (In order, preorder, postorder, DFS, BFS): three traversals, tree from inorder and postorder, DFS vs BFS, path graph, DFS reachability proof; Nov 2019, Jun 2020, Jun 2022, Jun 2023, Nov 2023, Jun 2025.
  • NP-completeness: P vs NP, reduction, Cook, subset-sum algorithm, Hamiltonian cycle, colouring, vertex cover; May 2019, Dec 2020, Jun 2022, Jun 2025, Jun 2026.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in