CODEWITHSUNDEEP
javabinary-search-tree
Ryan Sayles
Ryan Sayles

Reputation: 3431

Adding objects to binary search tree

I'm completely new to BST and how they work if this is completely wrong it would be appreciated if I could get a link to a reference site or something. right now I'm writing a program to add values from an ArrayList of Strings to a BST and I come up with errors such as The method compareTo(Node) is undefined for the type ArrayList<String>. I thought by having extends Comparable it would account for comparing ArrayList values but I'm not using E. Also I had to add a cast to s to set it as the root but I feel like there is an easier way. I don't know if I can add ArrayList values the way I'm doing it, this is just how it looks in the book I'm using for reference. This is my code, any help would be appreciated, I already tried looking up things in the Java API and that didn't help:

public class BinarySearchTree<E extends Comparable<? super E>>

{

    public void add(ArrayList<String> s, Node n) {


            if (n == null)
                 n = (Node) s;
            else if (s.compareTo(n) < 0)
                 add(s, n.leftChild);
            else
                 add(s, n.rightChild);


    }
}

Upvotes: 1

Views: 8224

Answers (3)

user1270627
user1270627

Reputation:

I think this reference would be helpful to you: Binary Search Trees - Stanford Library

Upvotes: 1

Noroi
Noroi

Reputation: 71

First of all, the Node class should extend Comparable and override the compareTo method in it. ArrayList class doesn't extend Comparable and hence the following will not work

s.compareTo(n) < 0

s being an ArrayList reference. Also, you are trying to compare an ArrayList reference with a Node reference which is totally incorrect. You need to compare two Node values.

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234795

It looks like you are trying to add the entire ArrayList as a single node of your BST. My guess is that you are supposed to construct a BST from the elements of the ArrayList. For that, I would suggest defining two functions:

public Node add(ArrayList<String> s, Node root) {
    for (String elt : s) {
        root = add(elt, root);
    }
}

public Node add(String elt, Node root) {
    if (root == null) {
        root = // new Node with data set to elt
    } else if (elt.compareTo(n.data()) < 0) {
        root.left = add(elt, root.left);
    } else if (elt.compareTo(n.data()) > 0) {
        root.right = add(elt, root.right);
    } else {
        // duplicate element being inserted -- error?
    }
    return root;
}

Upvotes: 0

Related Questions