Created
March 17, 2014 16:26
-
-
Save manuel-sugawara/9602702 to your computer and use it in GitHub Desktop.
Write a function that, given two nodes and a tree root, finds the two nodes' lowest common ancestor. That is, the function should find the ancestor that both nodes share that is furthest away from the root.
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 two nodes and the root of a tree find their lowest | |
* common ancestor. | |
*/ | |
public Node findLowestCommonAncestor(Node root, Node a, Node b) { | |
// If either a or b are the root, then the root is the lowest common ancestor. | |
if (a == root || b == root) { | |
// Not sure if this is a correct answer. It depends on | |
// whether you allow a node to be ancestor of itself or | |
// not. If the former the answer is correct, else null | |
// will be more appropriate. | |
return root; | |
} | |
Stack<Node> aStack = pathToRoot(a); | |
Stack<Node> bStack = pathToRoot(b); | |
Node ansestor = root; | |
while (!aStack.empty() && !bStack.empty()) { | |
Node anode = aStack.pop(); | |
Node bnode = bStack.pop(); | |
if (anode != bnode) { | |
return ansestor; | |
} | |
ansestor = anode; | |
} | |
return ansestor; | |
} | |
public static Stack<Node> pathToRoot(Node node) { | |
Stack<Node> stack = new Stack<Node>(); | |
Node tmp = node; | |
while (tmp.parent != null) { | |
stack.push(tmp.parent); | |
tmp = tmp.parent; | |
} | |
return stack; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment