Question

Consider a complete binary tree with 7 nodes. Let \( A \) denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let \( B \) denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root. The value of \( |A - B| \) is \(\underline{\hspace{2cm}}\).

Hint:

BFS explores nodes level-wise, while DFS goes deep before backtracking, leading to different early traversal sets.

Answer 1

Correct Answer: 1

Step 1: Structure of a complete binary tree with 7 nodes.
A complete binary tree with 7 nodes has one root, two children at level 1, and four children at level 2.

Step 2: BFS traversal (level-order).
BFS visits nodes level by level. The first 3 nodes visited are:
\[ A = \{\text{root}, \text{left child}, \text{right child}\} \]

Step 3: DFS traversal (preorder).
DFS (starting from root) visits:
\[ \text{root} \rightarrow \text{left child} \rightarrow \text{left-left child} \] Thus, \[ B = \{\text{root}, \text{left child}, \text{left-left child}\} \]

Step 4: Compute set difference.
\[ A - B = \{\text{right child}\} \] \[ |A - B| = 1 \] % Final Answer

Final Answer: \[ \boxed{1} \]