/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // search
        // search in a binary tree
        // array of size 2, p -- 1,2 q -- 1,2
        // p - 1, q - 2 stop
        // p - 1, q - 1 left
        // p - 2, q - 2 right

    public int search(TreeNode root, TreeNode node) {
        if(root == null) return 0;

        if(root == node) return 1;

        int left = search(root.left, node);
        if(left == 1) return left;
        int right = search(root.right, node);
        if(right == 1) return right;

        return 2;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return root;
        }

        if(root == p) {
            return p;
        }
        if(root == q) {
            return q;
        }

        int dirp = search(root.left, p);
        int dirq = search(root.left, q);

        System.out.println(dirp + " " + dirq);

        if((dirp == 1 && dirq == 2) || (dirp == 2 && dirq == 1)) {
            return root;
        }

        if(dirp == 1 && dirp == 1) {
            return lowestCommonAncestor(root.left, p, q);
        }

        if(dirp == 2 && dirp == 2) {
            return lowestCommonAncestor(root.right, p, q);
        }

        return null;
    }
}