LearnFrenzy
Sign in Take a free test

Data Structures in Java · Data Structures in Java Output Questions · Question 9

Level-order traversal printed level by level Answer, explanation & discussion

  • Output
  • Medium
  • 0 comments
  • Answer explained
  • Moderated community
Question 9 Back to Exercise

What is the output of the following Java program?

Main.java
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!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links