Question 26

Consider a 7-node complete binary tree labeled in level order:

• Root: 1
• Level 1: Left child 2, Right child 3
• Level 2: Children of 2 are 4 and 5; children of 3 are 6 and 7.

BFS visits nodes level by level:

• Step 1: node 1 (root)
• Step 2: node 2 (first child in level 1)
• Step 3: node 3 (second child in level 1)
  Thus, the set of the first 3 elements visited by BFS is $A = \{1, 2, 3\}$.

DFS explores deeply along a branch first:

• Starting from root 1, it visits child 2, and then proceeds to the child of 2 (node 4 or 5).
• Thus, the set of first 3 elements visited by DFS is $B = \{1, 2, 4\}$ (or $\{1, 2, 5\}$ if right child visited first, or $\{1, 3, 6\} / \{1, 3, 7\}$ if right subtree explored first).

In any standard DFS traversal:

• Root 1 is in both $A$ and $B$.
• Exactly one child of the root (node 2 or node 3) is visited in the first 3 steps, and the third node visited in DFS is a grandchild (from level 2).
• Therefore, $A \cap B$ contains exactly 2 nodes (the root and one child), while the other child of the root is in $A$ but not in $B$.

Consequently, $|A - B| = 3 - 2 = 1$.