Finding a common node with key between two different BinarySearchTrees

Question

I am currently trying to write methods that checks all the nodes in two different Binary Search trees and find nodes with common keys between the two trees. (i.e. trying to find a node from tree 1 and a node from tree 2 that contains the same keys. If a common node is found, the method returns true, otherwise it returns false. The second tree is stored in a different object than tree 1, called GraphicalObject. And the key is in the form of coordinates and size comparason is done using column order.

I have written the following code, but wondering if there is anything wrong with it or if there is anything I could improve up on?

1) A method that checks if a node from tree 1 is the same as every node in tree 2 using recursive calls. the compareTo method is defined else where.

public boolean findPixel(BinaryNode node1, BinaryNode node2, GraphicalObject gobj) {
    //Creating the final coordinate key by altering the original key in nodes of tree 2.
    int xCor = node2.getData().getLocation().xCoord() + gobj.getOffset().xCoord() - graphicPos.xCoord();
    int yCor = node2.getData().getLocation().yCoord() + gobj.getOffset().yCoord() - graphicPos.yCoord();
    Location newLoc = new Location(xCor, yCor); //Creates the final key to be checked up on
    if(node1.getData().getLocation().compareTo(newLoc) == 0) { //If keys are the same
        return true;
    } else {
        if(node1.getData().getLocation().compareTo(newLoc) == -1) { //if key from node 1 is smaller than key from node 2.
            node2 = node2.getLeft();
            findPixel(node1, node2, gobj);
        } else {
            node2 = node2.getRight();
            findPixel(node1, node2, gobj);
        }
    }
    return false; 
}

2) A method that uses findPixel method to check every node in tree 1 and compare them to every node in tree 2, using inorder traversal.

private boolean findCommonNode(BinaryNode node1, BinaryNode node2, GraphicalObject gobj) {
    if(node1 != null) {
        findCommonNode(node1.getLeft(), node2, gobj);
        return findPixel(node1, node2, gobj);
        findCommonNode(node1.getRight(), node2, gobj);
    }
}

3) method that returns true if common node between the two trees is found, or false otherwise.

public boolean intersects(GraphicalObject gobj){
    BinaryNode tempNode = newTree.getRoot();
    BinaryNode tempNode2 = gobj.getTree().getRoot();
    if (findCommonNode(tempNode, tempNode2, gobj) == true) {
        return true;
    } else {
        return false;
    }
}

Is there anything wrong with this code? Or is there anything I could do to make it better or run more efficiently?

Answer 1

There are couple of things that seem wrong in your code:

In the first method you calling recursive call to findPixel - you need to return the answer of the method back. It should be like this:

} else {
    if(node1.getData().getLocation().compareTo(newLoc) == -1) 
        return findPixel(node1, node2.getLeft(), gobj);
    else
        return findPixel(node1, node2.getRight(), gobj);
}
return false; 

You should also add check for null for node2 before extract the location. Add this to the first line of findPixel function:

if (node2 == null)
    return false;

On your second method, you using return statement inside the function -> therefor you will not get inorder traversal but it will ignore the right side of the tree. That code need to be as follow:

if(node1 != null) {
    return (findCommonNode(node1.getLeft(), node2, gobj)) ||  (findPixel(node1, node2, gobj)) || (findCommonNode(node1.getRight(), node2, gobj));
}

This way you can save some running time (if the answer is true no need to continue looking for more similar nodes).

Last, third method can be modify to (readability):

BinaryNode tempNode = newTree.getRoot();
BinaryNode tempNode2 = gobj.getTree().getRoot();
return (findCommonNode(tempNode, tempNode2, gobj));

This for your given code.

However, more optimize solution will be to traverse on one tree and insert there value (after hash) in hash-map - then traverse on the second tree and for each node: check if he exist in the hash-map. this will be O(n) complexity in contrast to your solution which is O(n^2).

Hope this help!