/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode lca;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        search(root, p, q, 0);
        return lca;
    }

    private int search(TreeNode root, TreeNode p, TreeNode q, int state) {
        System.out.println("going " + root.val +  " state " + state);
        if (root == p) {
            System.out.println("found p");
            state &= 1;
        }
        else if (root == q) {
            System.out.println("found q");
            state &= 2;
        }
        if (state != 3 && root.left != null) {
            System.out.println("go left " + root.left.val);
            state &= search(root.left, p, q, state);
        }

        if (state != 3 && root.right != null) {
            System.out.println("go right " + root.right.val);
            state &= search(root.right, p, q, state);
        }

        if (state == 3) {
            lca = root;
        }

        return state;
    }
}