CareerCup

public class BST{
public Integer value = null;
public BST left = null;
public BST right = null;

public static void main(String[] args) {
int[] base = {1, 3, 2, 4};
int[] alternative = {1, 3, 4, 2};
BST root = createBST(base);
BST alter = createBST(alternative);
System.out.println(checkIfBSTEqual(root,alter));
printDepthDifference(root,alter);
}

private static boolean checkIfBSTEqual(BST root, BST alter) {
if (root == null && alter == null) {
return true;
} else if (root == null && alter != null) {
return false;
} else if (root != null && alter == null) {
return false;
} else return (checkIfBSTEqual(root.left,alter.left) && checkIfBSTEqual(root.right,alter.right));
}

private static void printDepthDifference(BST root, BST alter) {
int depth = findDepth(root);
int depth2 = findDepth(alter);
System.out.println(depth2 - depth);
}

private static int findDepth(BST root) {
int left = 1;
int right = 1;
if (root.left != null) {
left = findDepth(root.left);
}
if (root.right != null) {
right = findDepth(root.right);
}
return Math.max(left, right);
}

private static BST createBST(int[] base) {
BST root = new BST();
root.value = base[0];
for (int i = 1; i < base.length; i++) {
BST temp = root;
int val = base[i];
boolean pos = false;
while (!pos) {
if (val > temp.value) {
if (temp.right !=null) {
temp = temp.right;
} else {
BST newBST = new BST();
newBST.value = val;
temp.right = newBST;
pos = true;
}
} else {
if (temp.left !=null) {
temp = temp.left;
} else {
BST newBST = new BST();
newBST.value = val;
temp.left = newBST;
pos = true;
}
}
}
}
return root;
}
}

boolean same_topo_tree(Node *r1, Node *r2) {
   if(!r1 != !r2) return false; /* (r1&&!r2) || (r2 && !r1) */
   return (same_topo_tree(r1->left, r2->left) && 
              same_topo_tree(r1->right, r2->right) ) ||
             (same_topo_tree(r1->left, r2->right) && 
              same_topo_tree(r1->right, r2->left) );
}