// Given parent node, we can start from nodes A and B and trace back to the root node and record the 
    //path from nodes A and B to root in a stack; and then, pop the stacks until their paths nodes are different:
    // the last node that are the same on their paths is the LCA;
class Solution {
public:
    /*
     * @param head: the List
     * @param k: rotate to the right k places
     * @return: the list after rotation
     */
    ParentTreeNode *lowestCommonAncestorII(ParentTreeNode *root,
                                           ParentTreeNode *A,
                                           ParentTreeNode *B) {
        // Write your code here
        stack<ParentTreeNode*> pathA = findPathToRoot(A);
        stack<ParentTreeNode*> pathB = findPathToRoot(B);

        ParentTreeNode *LCA = NULL;

        while (!pathA.empty() && !pathB.empty() && pathA.top() == pathB.top()) {
            LCA = pathA.top();
            pathA.pop();
            pathB.pop();
        }
        return LCA;
    }

    stack<ParentTreeNode*> findPathToRoot(ParentTreeNode *node) {
        stack<ParentTreeNode*> path;
        while (node != NULL) {
            path.push(node);
            node = node->parent;
        }
        return path;
    }
};