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.

gistfile1.java

    /**
     * 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;
    }