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}}\).
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}}\).
Show Hint
BFS explores nodes level-wise, while DFS goes deep before backtracking, leading to different early traversal sets.
Updated On: Feb 2, 2026
Show Solution
Verified By Collegedunia
Correct Answer: 1
Solution and Explanation
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} \]
Was this answer helpful?
0
0
Top GATE CS Algorithms Questions
- Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph \( G \) is/are TRUE?
- Let \( G \) be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant \( \alpha \) is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in \( G \) before and after the edge weight update?
- Consider the following recurrence relations. For all \(n > 1\),
\[ T_1(n) = 4T_1\left(\frac{n}{2}\right) + T_2(n) \]
\[ T_2(n) = 5T_2\left(\frac{n}{4}\right) + \Theta(\log_2 n) \]
Assume that for all \(n \leq 1\), \(T_1(n) = 1\) and \(T_2(n) = 1\).
Which one of the following options is correct? - Let \(G(V,E)\) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.
Let \(s \in V\) be a vertex in \(G\). For every \(u \in V\) and for every \(k \geq 0\), let \(d_k(u)\) denote the weight of a shortest path (in terms of weight) from \(s\) to \(u\) of length at most \(k\). If there is no path from \(s\) to \(u\) of length at most \(k\), then \(d_k(u) = \infty\).
Consider the statements:
S1: For every \(k \geq 0\) and \(u \in V\), \(d_{k+1}(u) \leq d_k(u)\).
S2: For every \((u,v) \in E\), if \((u,v)\) is part of a shortest path (in terms of weight) from \(s\) to \(v\), then for every \(k \geq 0\), \(d_k(u) \leq d_k(v)\).
Which one of the following options is correct? - Let \(G(V, E)\) be a simple, undirected graph. A vertex cover of \(G\) is a subset \(V' \subseteq V\) such that for every \((u, v) \in E\), \(u \in V'\) or \(v \in V'\). Let the size of the smallest vertex cover in \(G\) be \(k\). Let \(S\) be any vertex cover of size \(k\).
For a vertex \(v \in V\), which of the following constraints will always ensure that \(v \in S\)?
View More Questions
Top GATE CS Graph traversals Questions
- Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph \( G \) is/are TRUE?
- Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph \(G(V,E)\) as input, where \(d[v]\) and \(f[v]\) are the discovery time and finishing time, respectively, of the vertex \(v \in V\).
DFS(G): unmark all v in V t <- 0 for each v in V if v is unmarked t <- Explore(G, v, t) end if end for Explore(G, v, t): mark v t <- t + 1 d[v] <- t for each (v, w) in E if w is unmarked t <- Explore(G, w, t) end if end for t <- t + 1 f[v] <- t return tSuppose that the input directed graph \(G(V,E)\) is a directed acyclic graph (DAG).
For an edge \((u,v) \in E\), which of the following options will NEVER be correct?
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions