Consider a complete binary tree with 7 nodes. Let A denote the set of first 3…
2021
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 _____________ .
Attempted by 105 students.
Show answer & explanation
Correct answer: 1
Key idea: list the first three nodes visited by BFS (level-order) and by DFS (pre-order), then compare the sets.
BFS (level-order): visit the root, then its left child, then its right child. The first three nodes are {root, left child, right child}.
DFS (pre-order, root-left-right): visit the root, then its left child, then that left child’s left child. The first three nodes are {root, left child, left-left child}.
Compare sets: A = {root, left child, right child}, B = {root, left child, left-left child}. A − B = {right child}, so |A − B| = 1.
A video solution is available for this question — log in and enroll to watch it.