/*
    Node structure
    class Node{
        public Node left,right; // for left and the right child !!
        public int data;
    }

    */
    int lca(Node root, Node a, Node b){

        if(a == b) return a.data;

        Node ancestor = null;

        GetLowestCommonAncestorHelper(root, a, b, ref ancestor);

        if(ancestor == null) return -1;

        return ancestor.data;
    }

     TreeInfo GetLowestCommonAncestorHelper(Node node, Node p, Node q, ref Node ancestor) {
        if(node == null) return new TreeInfo(false, 0);

        var leftInfo = GetLowestCommonAncestorHelper(node.left, p, q, ref ancestor);
        var righInfo = GetLowestCommonAncestorHelper(node.right, p, q, ref ancestor);

        var treeInfo =  new TreeInfo(false, 0);

        if(leftInfo.isAncestor && righInfo.isAncestor)
        {
            if(leftInfo.count == 2) return leftInfo;

            else if(righInfo.count == 2) return righInfo;

            treeInfo.isAncestor = true;
            treeInfo.count = 2;
            ancestor = node;
            return treeInfo;
        }
        else
        {
            if(node == p || node == q)
            {
                treeInfo.isAncestor = true;
                treeInfo.count = 1;
            }

            if(leftInfo.isAncestor || righInfo.isAncestor)
            {
                treeInfo.isAncestor = true;
                treeInfo.count += 1;
            }

            if(treeInfo.count == 2) ancestor = node;
        }

        return treeInfo;
    }

    class TreeInfo{
        public bool isAncestor = false;
        public int count;
        public TreeInfo(bool isAncestor, int count){this.isAncestor = isAncestor; this.count = count;}
    }