LearnFrenzy
Sign in Take a free test

Generics · Generics Programs · Question 8

Generic binary search tree in Java Solution, output & explanation

  • Program
  • Hard
  • 0 comments
  • Answer explained
  • Moderated community
Question 8 Back to Exercise

Implement a generic binary search tree BST<T extends Comparable<T>> with insert (ignoring duplicates), contains, in-order traversal and height; test with integers and strings.

Solution
Main.java
import java.util.ArrayList;
import java.util.List;

class BST<T extends Comparable<T>> {
    private class Node {
        final T value;
        Node left, right;
        Node(T v) { value = v; }
    }

    private Node root;
    private int size;

    void insert(T v) { root = insert(root, v); }
    private Node insert(Node n, T v) {
        if (n == null) { size++; return new Node(v); }
        int c = v.compareTo(n.value);
        if (c < 0) n.left = insert(n.left, v);
        else if (c > 0) n.right = insert(n.right, v);
        return n;
    }

    boolean contains(T v) {
        Node n = root;
        while (n != null) {
            int c = v.compareTo(n.value);
            if (c == 0) return true;
            n = c < 0 ? n.left : n.right;
        }
        return false;
    }

    List<T> inOrder() { List<T> out = new ArrayList<>(); walk(root, out); return out; }
    private void walk(Node n, List<T> out) { if (n == null) return; walk(n.left, out); out.add(n.value); walk(n.right, out); }

    int height() { return height(root); }
    private int height(Node n) { return n == null ? 0 : 1 + Math.max(height(n.left), height(n.right)); }
    int size() { return size; }
}

public class Main {
    public static void main(String[] args) {
        BST<Integer> t = new BST<>();
        for (int v : new int[]{50, 30, 70, 20, 40, 60, 80, 30, 65}) t.insert(v);
        System.out.println(t.inOrder() + " size=" + t.size() + " height=" + t.height() + " " + t.contains(65) + " " + t.contains(55));

        BST<String> words = new BST<>();
        for (String w : "the quick brown fox jumps over the lazy dog".split(" ")) words.insert(w);
        System.out.println(words.inOrder() + " size=" + words.size());
    }
}

Output Verified by compiling and running

[20, 30, 40, 50, 60, 65, 70, 80] size=8 height=4 true false
[brown, dog, fox, jumps, lazy, over, quick, the] size=8

The bound T extends Comparable lets the tree compare any element type; the in-order walk returns sorted values.

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