I should create a equals() method that will compare two trees against each other. No matter what the order of the second tree, if it contains all the elements of the first tree it should return true.
I've already made one equals() method that will return true if two trees are identical, see my code below. My approach was, with recursion, to work my way up through the second tree and compare it to one node of the first tree. If I got a match I would return true and continue with another node from my first tree. If I ever got through the second tree without a match I would return false.
My code for comparing if two trees are equal:
public boolean equals(BST t) {
return equalsTree(root, t.root);
}
public boolean equalsTree(Node r, Node t){
if(r == null && t == null){
return true;
}else if((r != null && t == null) || (r==null && t != null)){
return false;
}else{
return t.key.equals(r.key) && (equalsTree(r.left,t.left)) && (equalsTree(r.right, t.right));
}
}
You have the right idea. You need to compare if both the left and the right branches match up. If they don't compare the opposite sides.
| 1 | { | { |
| 2 | v: 0 | v: 0 |
| 3 | l: { | l: { |
| 4 | v: 1, | v: 2 |
| 5 | l: null | l: null |
| 6 | r: null | r : { |
| 7 | }, | v: 3 |
| 8 | r: { | l: null |
| 9 | v: 2 | r: null |
| 10 | l: { | } |
| 11 | v: 3 | } |
| 12 | l: null | r: { |
| 13 | r: null | v: 1 |
| 14 | }, | l: null |
| 15 | r: null | r: null |
| 16 | } | } |
| 17 | } | } |
As you can see above, both root nodes have a value of zero, but their opposite branches have identical nodes. The right node (2) of the first tree has a left node with the value of (3). The left node (2) of the second tree also has a child node of the value (3), but it's right. Since the order does not matter, both trees are equal.
public class TreeCompare {
public static void main(String[] args) {
Tree<Integer> treeA = new Tree<Integer>();
Tree<Integer> treeB = new Tree<Integer>();
Node<Integer> treeArootNode = new Node<Integer>(0);
Node<Integer> treeBrootNode = new Node<Integer>(0);
Node<Integer> treeAnode1 = new Node<Integer>(1);
Node<Integer> treeAnode2 = new Node<Integer>(2);
Node<Integer> treeAnode3 = new Node<Integer>(3);
Node<Integer> treeBnode1 = new Node<Integer>(1);
Node<Integer> treeBnode2 = new Node<Integer>(2);
Node<Integer> treeBnode3 = new Node<Integer>(3);
treeA.root = treeArootNode;
treeB.root = treeBrootNode;
treeA.root.left = treeAnode1;
treeA.root.right = treeAnode2;
treeB.root.left = treeBnode2;
treeB.root.right = treeBnode1;
treeAnode2.left = treeAnode3;
treeBnode2.right = treeBnode3; // or treeBnode2.left
System.out.println(treeA);
System.out.println(treeB);
System.out.println(treeA.equals(treeB));
}
}
public class Tree<T> {
public Node<T> root;
@SuppressWarnings("unchecked")
public boolean equals(Object other) {
Tree<T> otherTree = (Tree<T>) other;
if (other == null) return false;
if (this.root == null && otherTree.root != null) return false;
if (this.root != null && otherTree.root == null) return false;
return equalsNode(this.root, otherTree.root);
}
public boolean equalsNode(Node<T> nodeA, Node<T> nodeB) {
if (nodeA == null && nodeB == null) return true;
if (nodeA == null && nodeB != null) return false;
if (nodeA != null && nodeB == null) return false;
if (nodeA.equals(nodeB)) {
if (nodeA.value == null && nodeB.value != null) return false;
if (nodeA.value != null && nodeB.value == null) return false;
if (nodesEqualSameLeft(nodeA, nodeB) && nodesEqualSameRight(nodeA, nodeB)) {
return equalsNode(nodeA.left, nodeB.left) && equalsNode(nodeA.right, nodeB.right);
}
if (nodesEqualOppositeLeft(nodeA, nodeB) && nodesEqualOppositeRight(nodeA, nodeB)) {
return equalsNode(nodeA.left, nodeB.right) && equalsNode(nodeA.right, nodeB.left);
}
}
return false;
}
public boolean nodesEqualSameLeft(Node<T> nodeA, Node<T> nodeB) {
return nodesEqual(nodeA.left, nodeB.left);
}
public boolean nodesEqualSameRight(Node<T> nodeA, Node<T> nodeB) {
return nodesEqual(nodeA.right, nodeB.right);
}
public boolean nodesEqualOppositeLeft(Node<T> nodeA, Node<T> nodeB) {
return nodesEqual(nodeA.left, nodeB.right);
}
public boolean nodesEqualOppositeRight(Node<T> nodeA, Node<T> nodeB) {
return nodesEqual(nodeA.right, nodeB.left);
}
public boolean nodesEqual(Node<T> nodeA, Node<T> nodeB) {
return (nodeA == null && nodeB == null) || (nodeA != null && nodeA.equals(nodeB));
}
@Override
public String toString() {
return root.toString();
}
}
public class Node<T> {
public Node<T> left;
public Node<T> right;
public T value;
public Node(Node<T> left, Node<T> right, T value) {
this.left = left;
this.right = right;
this.value = value;
}
public Node(T value) {
this(null, null, value);
}
@Override
@SuppressWarnings("unchecked")
public boolean equals(Object other) {
Node<T> otherNode = (Node<T>) other;
if (other == null) return false;
if (this.value == null && otherNode.value != null) return false;
if (this.value != null && otherNode.value == null) return false;
return this.value.equals(otherNode.value);
}
@Override
public String toString() {
return String.format("{ \"v\" : %s, \"l\" : %s, \"r\" : %s }", value, left, right);
}
}
{ "v" : 0, "l" : { "v" : 1, "l" : null, "r" : null }, "r" : { "v" : 2, "l" : { "v" : 3, "l" : null, "r" : null }, "r" : null } }
{ "v" : 0, "l" : { "v" : 2, "l" : null, "r" : { "v" : 3, "l" : null, "r" : null } }, "r" : { "v" : 1, "l" : null, "r" : null } }
true