GATE CS 2021 Set 2 Q16 — Trees

Let the 7 nodes of the complete binary tree be represented as follows, where 1 is the root:

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

1. Breadth-First Search (BFS):

BFS visits the nodes level-by-level from left to right. The first 3 elements visited are 1, 2, and 3.
Therefore, the set $A = \{1, 2, 3\}$.

2. Depth-First Search (DFS):

DFS starting from the root visits a child and then goes deeper to a grandchild before backtracking. Depending on whether we traverse left-first or right-first:

• If left-first: The first 3 elements visited are 1, 2, and then either 4 or 5. Thus, $B = \{1, 2, 4\}$ or $B = \{1, 2, 5\}$.
• If right-first: The first 3 elements visited are 1, 3, and then either 6 or 7. Thus, $B = \{1, 3, 6\}$ or $B = \{1, 3, 7\}$.

3. Calculating $|A - B|$:

• If $B = \{1, 2, 4\}$, then $A - B = \{3\}$, so $|A - B| = 1$.
• If $B = \{1, 3, 6\}$, then $A - B = \{2\}$, so $|A - B| = 1$.

In all possible DFS traversals, the cardinality of the set difference $|A - B|$ is exactly 1.