/* NOT passed be Leetcode: StackOverFlow
use DFS travesal the tree (recursion)
when hit p, store the DFS path into pStack
when hit q, store the DFS path into qStack
pop everythin from pStack, and check whether qStack contains it.
*/


public class Solution {
    private Stack<TreeNode> pStack = new Stack<TreeNode>();
    private Stack<TreeNode> qStack = new Stack<TreeNode>();
    private Stack<TreeNode> tempStack = new Stack<TreeNode>();
    private int count = 0;
    private TreeNode res = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        preOrder(root, p, q);

        while (!pStack.isEmpty()) {
            TreeNode pNode = pStack.pop();
            if (qStack.contains(pNode)) {
                res = pNode;
            }
        }

        return res;

    }

    private void preOrder(TreeNode root, TreeNode p, TreeNode q) {

        //base case
        if (root==null) {
            return;
        }
        tempStack.push(root);
        if (tempStack.peek()==p) {
            pStack = tempStack;
            count++;
        }
        if (tempStack.peek()==q) {
            qStack = tempStack;
            count++;
        }
        if (count==2) {
            return;
        }

        //recursive case
        preOrder(root.left, p, q);
        preOrder(root.right, p, q);

        tempStack.pop();

    }

}