LearnFrenzy
Sign in Take a free test

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

Height in edges, leaf count and node count Answer, explanation & discussion

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

What is the output of the following Java program?

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

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links