Java : How do I implement a generic Binary Search Tree?

Question

Until now, I have been writing a Node class as

class Node {
        private  value;
        private Node left;
        private Node right;

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

and Binary Search Tree as

public class BinarySearchTree {
    private Node root;

    public BinarySearchTree(int value) {
        root = new Node(value);
    }

    public void insert(int value) {
      Node node = new Node(value);
        // insert logic goes here to search and insert
    }
}

Now I would like to support BinarySearchTree to have insert node of any type like strings, people

How can I make it generic to hold any type?

What have you tried? Have you researched java generics and do you know about the syntax? — Colin D, Jun 29 '12 at 14:07

Petar Minchev · Answer 1 · 2012-06-29T14:18:53.387

17

Use generics:

class Node<T extends Comparable<T>> {
        private T value;
        ...
}

public class BinarySearchTree<T extends Comparable<T>> {
    private Node<T> root;

    public BinarySearchTree(T value) {
        root = new Node<T>(value);
    }

    public void insert(T value) {
      Node<T> node = new Node<T>(value);
        // insert logic goes here to search and insert
    }
}

edited Jun 29 '12 at 14:18

answered Jun 29 '12 at 14:06

Petar Minchev

46,889
11
103
119

3

Dunno who is the down voter, but pay attention that you must enforce T to extend comparable, otherwise it will be impossible to implement the comparison code. – Yair Zaslavsky Jun 29 '12 at 14:14

Tudor · Answer 2 · 2012-06-29T14:16:02.740

Just make each of the Node and BinarySearchTree classes generic:

class Node<T extends Comparable<T>> {
    private T value;
    private Node<T> left;
    private Node<T> right;

    public Node(T value) {
        this.value = value;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }
}

and:

class BinarySearchTree<T extends Comparable<T>> {
    private Node<T> root;

    public BinarySearchTree(T value) {
        root = new Node<T>(value);
    }

    public void insert(T value) {
      Node<T> node = new Node<T>(value);
        // insert logic goes here to search and insert
    }
}

Note the Comparable extension constraint that you will need later to enforce node ordering in the tree. Thanks to zaske for the suggestion.

You must enforce T to extend comparable, or to provide Comprable at the CTOR, otherwise you will not be able to perform the search. — Yair Zaslavsky, Jun 29 '12 at 14:13

Victor · Answer 3 · 2016-09-17T18:52:12.773

Please find the BST using Generics, U can find more information on below link

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/code/BST.java

public class BinarySearchTree< T extends Comparable<T>> {
    Node root;
    class Node {
        T data;
        Node left;
        Node right;

        public Node(T data) {
            this.data = data;
        }
    }

    public boolean isEmpty() {
        return root == null;
    }

    public void insert(T value) {
        if(isEmpty())
            root = new Node(value);
        else
            insert(root, value);
    }

    private void insert(Node node, T value) {

        if(value.compareTo(node.data) < 0) {
            if(node.left == null)
                node.left = new Node(value);
            else
                insert(node.left, value);
        }
        else {
            if(node.right == null)
                node.right = new Node(value);
            else
                insert(node.right, value);
        }
    }

}

score 1 · Answer 4 · answered Jun 29 '12 at 14:12

Please not your code does not compile.
You have a few challenges here -
A. Define Node as Generic -

public class Node<T> {
   private T value;
   //... here goes the rest of your code
}

B. Your search class also should be generic, and the signature should be

public class BinarySearchTree <T extends Comparable<T>> {

   public BinarySearchTree(T value) {
      //Do your logic here
   }

   public void insert(T value)  {
        //Do your logic here
   }
}

This is required in order to enforce you to provide only types that implement Comparable so you will be able to perform the search in the tree.

@trumpetlicks - No. There is no code inside the class of Node that needs methods of Comparable. Of course, When using BinaryTreeSearch, there will be no way to create Nodes of classes that do not implement Compparable. — Yair Zaslavsky, Jun 29 '12 at 16:37

score 0 · Answer 5 · answered Jun 29 '12 at 14:07

0

You have two options:

1) You can get into generics/templates.

2) Have your tree take in a type Object instead of int and have the user be responsible for casting.

answered Jun 29 '12 at 14:07

namenamename

195
7

score 0 · Answer 6 · answered May 13 '16 at 17:18

0

I found a SnapTreeMap that implements a concurrent AVL tree system here.

answered May 13 '16 at 17:18

adv

357
5
18

score 0 · Answer 7 · answered May 27 '18 at 04:04

public class TNode<T extends Comparable<T>> {
    T data;
    public TNode<T> left;
    public TNode<T> right;

    public TNode(T data){
        this.data = data;
    }
}


import java.util.ArrayList;
import java.util.List;

public class BinaryTree<T extends Comparable<T>> {
private TNode root;

public TNode getRoot() {
    return this.root;
}

public void add(T data) {
    TNode<T> newNode = new TNode<T>(data);
    if (root == null) {
        root = newNode;
    } else {
        TNode<T> tempNode = root;
        TNode<T> prev = null;
        while (tempNode != null) {
            prev = tempNode;
            if (data.compareTo(tempNode.data) > 0) {
                tempNode = tempNode.right;
            } else {
                tempNode = tempNode.left;
            }
        }
        if (data.compareTo(prev.data) < 0) {
            prev.left = newNode;
        } else {
            prev.right = newNode;
        }

    }
}


public void traverseInOrder(TNode<T> root, List<T> storageList) {
    if (root != null) {
        traverseInOrder(root.left, storageList);
        storageList.add(root.data);
        traverseInOrder(root.right, storageList);
    }
}

public void traversePreOrder(TNode<T> root, List<T> storageList) {
    if (root != null) {
        storageList.add(root.data);
        traversePreOrder(root.left, storageList);
        traversePreOrder(root.right, storageList);
    }
}

public void traversePostOrder(TNode<T> root, List<T> storageList) {
    if (root != null) {
        traversePostOrder(root.left, storageList);
        traversePostOrder(root.right, storageList);
        storageList.add(root.data);
    }
}

public void printList(List<T> list) {
    for (T item : list) {
        System.out.println(item);
    }
}


public static void main(String args[]) {
    BinaryTree<Integer> bTree = new BinaryTree<>();
    bTree.add(50);
    bTree.add(30);
    bTree.add(60);
    bTree.add(25);
    bTree.add(40);
    bTree.add(35);
    bTree.add(70);
    bTree.add(65);

    System.out.println("#### Inorder Traversal ####");
    List<Integer> inOrderList = new ArrayList<>();
    bTree.traverseInOrder(bTree.getRoot(), inOrderList);
    bTree.printList(inOrderList);

    System.out.println("#### Pre Traversal ####");
    List<Integer> preOrderList = new ArrayList<>();
    bTree.traversePreOrder(bTree.getRoot(), preOrderList);
    bTree.printList(preOrderList);


    System.out.println("#### Post Traversal ####");
    List<Integer> postOrderList = new ArrayList<>();
    bTree.traversePostOrder(bTree.getRoot(), postOrderList);
    bTree.printList(postOrderList);


}

Considering that this is a question from 2012, you should highlight what you bring with your code, that other answers do not already provide. A "code dump" without explanations is not super useful. — Nic3500, May 27 '18 at 04:31

score 0 · Answer 8 · answered Jan 30 '22 at 15:20

Wrote this recently. I hope you find it useful

public class TreeMap<V extends Comparable<V>> {

private class Node {
    Node left, right;
    V value;
    public Node(V value) {
        this.value = value;
    }
}

private Node root;
private int size;

public int getSize() {
    return size;
}

public TreeMap() {
    this.root = null;
    this.size = 0;
}

public boolean isEmpty() {
    if (root == null) return true;
    else return false;
}

public void insert(V value) {
    size++;
    if (isEmpty()) root = new Node(value);
    else insert(root, value);
}

public boolean contains(V value) {
    return contains(root, value);
}

public void print() {
    print(root);
}

private boolean contains(Node node, V value) {
    if (value.compareTo(node.value) == 0) {
        return true;
    } else if (value.compareTo(node.value) < 0) {
        if (node.left == null) return false;
        else return contains(node.left, value);
    } else {
        if (node.right == null) return false;
        else return contains(node.right, value);
    }
}

private void print(Node node) {
    if (root == null) return;
    System.out.println(node.value);
    if (node.left != null) print(node.left);
    if (node.right != null) print(node.right);
}

private void insert(Node node, V value) {
    if(value.compareTo(node.value) <= 0) {
        if(node.left == null) node.left = new Node(value);
        else insert(node.left, value);
    } else {
        if(node.right == null) node.right = new Node(value);
        else insert(node.right, value);
    }
}

}

score 0 · Answer 9 · answered Jan 30 '22 at 15:47

Wrote this recently. I hope you find it useful

public class GenericBST<V extends Comparable<V>> {

private class Node {
    Node left, right;
    V value;
    public Node(V value) {
        this.value = value;
    }
}

private Node root;
private int size;

public int getSize() {
    return size;
}

public GenericBST() {
    this.root = null;
    this.size = 0;
}

public boolean isEmpty() {
    if (root == null) return true;
    else return false;
}

public void insert(V value) {
    size++;
    if (isEmpty()) root = new Node(value);
    else insert(root, value);
}

public boolean contains(V value) {
    return contains(root, value);
}

public void print() {
    print(root);
}

private boolean contains(Node node, V value) {
    if (value.compareTo(node.value) == 0) {
        return true;
    } else if (value.compareTo(node.value) < 0) {
        if (node.left == null) return false;
        else return contains(node.left, value);
    } else {
        if (node.right == null) return false;
        else return contains(node.right, value);
    }
}

private void print(Node node) {
    if (root == null) return;
    System.out.println(node.value);
    if (node.left != null) print(node.left);
    if (node.right != null) print(node.right);
}

private void insert(Node node, V value) {
    if(value.compareTo(node.value) <= 0) {
        if(node.left == null) node.left = new Node(value);
        else insert(node.left, value);
    } else {
        if(node.right == null) node.right = new Node(value);
        else insert(node.right, value);
    }
}

}

score -1 · Answer 10 · answered Jun 29 '12 at 14:07

Regaring second question you should use Template :

http://www.oracle.com/technetwork/articles/javase/generics-136597.html

Regarding first :

http://en.wikipedia.org/wiki/Binary_search_algorithm http://en.wikipedia.org/wiki/Tree_rotation (insert)

Maybe that's faster read:

http://www.roseindia.net/java/java-get-example/java-binary-tree-code.shtml

Good study!

Java : How do I implement a generic Binary Search Tree?

10 Answers10

Linked