Skip to content

Instantly share code, notes, and snippets.

@darrenrogan
Created September 4, 2013 04:48
Show Gist options
  • Save darrenrogan/6432857 to your computer and use it in GitHub Desktop.
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
//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