Created
September 4, 2013 04:48
-
-
Save darrenrogan/6432857 to your computer and use it in GitHub Desktop.
java algorithm, that searchs a tree for two nodes that have a difference k, and return the common ancestor
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Given a binary search tree | |
//write an algorith the common ancestor | |
//who's difference = k | |
//assume the value = int | |
public class Tree{ | |
TreeNode root; | |
int size; | |
... | |
getRoot() | |
} | |
public class TreeNode{ | |
int value; | |
TreeNode right; | |
TreeNode left; | |
... | |
getLeft() | |
getRight() | |
} | |
public class TestBstDifference{ | |
private Tree bst; | |
private int difference; | |
public TestBstDifference(Tree bst, int k){ | |
//error cases | |
if (bst == null) throw new Exception(); | |
if (bst.size() < 2) throw new Exception(); | |
if (k == 0) throw new Exception(); | |
this.difference = k; | |
this.bst = bst; | |
} | |
/* | |
* returns -1 if none found or the ancestor | |
*/ | |
public int findDifference(){ | |
TreeNode curNode = bst.getRoot(); | |
int result = processNodes(curNode); | |
return result; | |
} | |
private int processNodes(TreeNode curNode){ | |
int result = processNode(curNode); | |
if(result == 1){ | |
return result; | |
} | |
if(result ==-1){ | |
if(curNode.getLeft() != null){ | |
return processNodes(curNode.getLeft()); | |
}else{ | |
return result; | |
} | |
} | |
if(result ==-1){ | |
if(curNode.getRight() != null){ | |
return processNodes(curNode.getRight()); | |
}else{ | |
return result; | |
} | |
} | |
} | |
private int processNode(TreeNode node){ | |
int valuePlusDifference = node.value + difference; | |
if(findValue(bst.getRoot(),valuePlusDifference)){ | |
return findAncestor(bst.getRoot(),node.value,valuePlusDifference); | |
else{ | |
return -1; | |
} | |
} | |
} | |
private boolean findValue(TreeNode node, int value){ | |
if (node.value ==value){ | |
return true; | |
}else if (node.value > value){ | |
if (node.getLeft()==null) return false; | |
findValue(node.getLeft(),value); | |
}else if (node.value < value){ | |
if (node.getRight()==null) return false; | |
findValue(node.getRight(),value); | |
} | |
} | |
private int findAncestor(TreeNode node, int leftValue, int rightValue){ | |
TreeNode node = node; | |
if (node.value > leftValue && node.value < rigthValue){ | |
//found first ancestor | |
return node.value; | |
}else if (node.value < leftValue){ | |
if (node.getLeft()==null) throw new Exception(); | |
if (node.getLeft()==null) return 0 | |
findAncestor(node.getLeft(),leftValue,rightValue); | |
}else if (node.value > rightValue){ | |
if (node.getRight()==null) throw new Exception(); | |
// if (node.getRight()==null) return 0; | |
findAncestor(node.getRight(),leftValue,rightValue); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment