Question 9
Back to Exercise
What is the output of the following Java program?
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.StringJoiner;
public class Main {
static class Node {
int key;
Node left, right;
Node(int key) { this.key = key; }
}
static Node insert(Node n, int k) {
if (n == null) return new Node(k);
if (k < n.key) n.left = insert(n.left, k);
else n.right = insert(n.right, k);
return n;
}
public static void main(String[] args) {
Node root = null;
for (int k : new int[]{40, 20, 60, 10, 30, 50, 70, 25}) root = insert(root, k);
List<String> levels = new ArrayList<>();
Deque<Node> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
StringJoiner sj = new StringJoiner(" ");
for (int i = q.size(); i > 0; i--) {
Node n = q.poll();
sj.add(String.valueOf(n.key));
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
levels.add(sj.toString());
}
System.out.println(String.join(" | ", levels));
}
}
- A 40 | 20 60 | 10 25 30 50 70
- B 10 | 20 25 30 | 40 50 60 70
- C 40 20 10 30 25 60 50 70
- D 40 | 20 60 | 10 30 50 70 | 25 Correct
Correct Answer: Option D
q.size() is read once at the start of each level, so each pass of the outer loop prints exactly one level. 25 is the left child of 30.
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!