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

First, we must understand two traversal methods of a binary tree: Breadth-First Search (BFS) and Depth-First Search (DFS). A complete binary tree with 7 nodes can be structured as follows:

• Level 0: 1
• Level 1: 2, 3
• Level 2: 4, 5, 6, 7

BFS starts at the root and explores all nodes at the present level before moving to the next level. Following this, the BFS traversal would visit nodes in this order: 1, 2, 3, 4, 5, 6, 7. Hence, the first three elements for BFS are A = {1, 2, 3}. On the other hand, DFS explores as far as possible along each branch before backtracking, typically following a preorder traversal (root, left, right). For the given tree, the DFS traversal order is: 1, 2, 4, 5, 3, 6, 7. Thus, the first three elements for DFS are B = {1, 2, 4}. To find \( |A - B| \), we calculate the difference set \( A - B \), which includes elements in A not shared by B:

• \( A = \{1, 2, 3\} \)
• \( B = \{1, 2, 4\} \)
• \( A - B = \{3\} \)

Hence, \( |A - B| = 1 \). This value is within the given range of 1,1. Thus, the final answer is 1.