// You are here!  Your runtime beats 100.00 % of java submissions.

class Solution {
    TreeNode lca;

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

// govnokod ON
    private int search(TreeNode root, TreeNode p, TreeNode q, int state) {
        int s0, s1;

        if (root == p || root == q) {
            state++;
            if (state == 2) return 2;
            lca = root;
        }
        s0 = state;
        if (root.left != null) {
            state = search(root.left, p, q, state);
        }

        if (state == 2) return state;

        s1= state;

        if (root.right != null) {
            state = search(root.right, p, q, state);
        }

        if (state == 2 && s0 == 0 && s1 == 1) lca = root;

        return state;
    }
}