CODEWITHSUNDEEP
java
Aragorn300
Aragorn300

Reputation: 31

Checking for duplicate values in BinarySearchTree

I'm looking to continually look through my BinarySearchTree just in case there are duplicate values for File f, instead of ending once the first instance of File f is found. I need to return all instances of File f.

Right now this is my code for finding the File.

public File locateHelper(File f, Node<File> node) {
    if (node == null) {
        return null;
    }

    int result = f.compareTo(node.data);
    if (result == 0) {
        return f;
    }
    if (result < 0) {
        return locateHelper(f, node.leftChild);
    }

    return locateHelper(f, node.rightChild);

}

I've been trying to switch this to return possibly an ArrayList<File> instead of an individual file, but I keep running into NullPointerException problems.

How would you guys go about this?

Upvotes: 1

Views: 56

Answers (1)

Mike Nakis
Mike Nakis

Reputation: 61993

I would solve it with something like this:

public ArrayList<File> collectTree( Node<File> root )
{
    List<File> files = new ArrayList<>();
    collectTree( root, files );
    return files;
}

private void collectTree( Node<File> node, ArrayList<File> files )
{
    if( node == null )
        return;
    collectTree( node.leftChild, files );
    files.add( node.data );
    collectTree( node.rightChild, files );
}

This will return the contents of the entire tree in an ArrayList<File>.

Then, finding duplicates is a simple matter of walking the tree and checking adjacent elements.

You could do it without having to collect the entire tree inside an ArrayList, by using the visitor pattern, (look it up,) so instead of collecting nodes in a list you would be invoking some Consumer<File> which checks whether the file that it is currently being given is the same as the file that it was given in the last invocation.

Amendment

Okay, I am terribly sorry, I thought about it a bit more, (after my answer was upvoted and accepted,) and I came up with a much better solution which only involves searching for the first occurrence and then collecting only the duplicates.

It is based on the observation that once the first matching node is found, then all subsequent matching nodes will be either in the left subtree or in the right subtree of that node, but nowhere else in the entire tree. So:

  1. Do a simple search through the binary search tree to find the first matching node.

  2. Recursively collect all matching nodes from each subtree of that node.

Here is how it may look like. (Please note that I have not tested this, so it may contain little mistakes.)

public Collection<File> findAndCollectDuplicates( Node<File> root, File f )
{
    /* find a matching node; if none found, return an empty collection. */
    Node<File> node = findNode( root, f );
    if( node == null )
         return Collections.emptyList();

    /* collect duplicates and return them. */
    List<File> duplicates = new ArrayList<>();
    collectDuplicates( node, f, duplicates );
    return duplicates;
}

private Node<File> findNode( Node<File> root, File f )
{
    for(;;)
    {
        int result = f.compareTo( root.data );
        if (result == 0)
            return root;
        root = result < 0? root.leftChild : root.rightChild;
        if( root == null )
            return null;
    }
}

private void collectDuplicates( Node<File> node, File f, Collection<File> duplicates )
{
    if( node == null )
        return;
    if( f.compareTo( node.data ) != 0 )
        return;
    duplicates.add( node.data );
    collectDuplicates( node.leftChild );
    collectDuplicates( node.rightChild );
}

Upvotes: 2

Related Questions