Question 10
Back to Exercise
What is the output of the following Java program?
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;
}
static int height(Node n) { return n == null ? -1 : 1 + Math.max(height(n.left), height(n.right)); }
static int leaves(Node n) {
if (n == null) return 0;
if (n.left == null && n.right == null) return 1;
return leaves(n.left) + leaves(n.right);
}
static int count(Node n) { return n == null ? 0 : 1 + count(n.left) + count(n.right); }
public static void main(String[] args) {
Node root = null;
for (int k : new int[]{50, 30, 70, 20, 40, 80, 45}) root = insert(root, k);
System.out.println("height=" + height(root) + " leaves=" + leaves(root) + " nodes=" + count(root));
}
}
- A height=4 leaves=3 nodes=7
- B height=3 leaves=3 nodes=7 Correct
- C height=3 leaves=4 nodes=7
- D height=2 leaves=3 nodes=7
Correct Answer: Option B
An empty tree has height −1 here, so height counts edges: 50 → 30 → 40 → 45. The leaves are 20, 45 and 80.
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!