Skip to content
GATEiit

GATE CSE 2021 Set 2 Q26: BFS vs DFS: first three nodes of a 7-node complete binary tree

Question

Consider a complete binary tree with 7 nodes. Let AA denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let BB denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.

The value of ∣A−B∣|A - B| is ________.

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 1 (official GATE 2021 final answer key)

Concept used: BFS visits a whole level before going deeper; DFS goes down one branch first.

First step: BFS gives the root and its two children; DFS gives the root, one child and that child's child. Compare the two sets.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2021 Set 2 questions →