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());
}
}
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·
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!