CareerCup

If link to parent is not given then perform BFS while keep track of parents then build the path to each list of nodes from root ( say in linkedlist). traverse the linked list at the same time until current node is common across all lists

Either use segment tree RMQ on the Euler tour of the tree or use sqrt decomposition of the tree.
Note- both methods need preporcessing.

C#:

private Node CommonParentNode(Node ptr, List<Node> nodes)
        {
            if (ptr == null)
                return null;

            if (nodes.Contains(ptr))
                return ptr;

            Node left = CommonParentNode(ptr.left, nodes);
            Node right = CommonParentNode(ptr.right, nodes);

            if (left != null && right != null)
                return ptr;

            if (left == null && right == null)
                return null;

            return left ?? right;
        }

C#

private Node CommonParentNode(Node ptr, List<int> nodes)
        {
            if (ptr == null)
                return null;

            if (nodes.Contains(ptr.val))
                return ptr;

            Node left = CommonParentNode(ptr.left, nodes);
            Node right = CommonParentNode(ptr.right, nodes);

            if (left != null && right != null)
                return ptr;

            if (left == null && right == null)
                return null;

            return left ?? right;
	}

private TreeNode LCA(TreeNode root, List<TreeNode> nodes) {
return helper(root, nodes));
}

private TreeNode helper(TreeNode node, List<TreeNode> set) {
if(node == null) return null;
if(set.contains(node)) return node;
TreeNode left = helper(node.left, set);
TreeNode right = helper(node.right, set);
if(left != null && right != null) return node;
if(left == null) return right;
if(right == null) return left;
return null;
}

private TreeNode LCA(TreeNode root, List<TreeNode> nodes) {
        return helper(root, nodes);
    }
    
    private TreeNode helper(TreeNode node, List<TreeNode> set) {
        if(node == null)  return null;
        if(set.contains(node)) return node;
        TreeNode left = helper(node.left, set);
        TreeNode right = helper(node.right, set);
        if(left != null && right != null) return node;
        if(left == null) return right;
        if(right == null) return left;
        return null;
    }

1) Post order like traversal where all parents are in a stack when a node is visited.
2) When each node in lstpNodes is visited, record the size of the stack. Pick out the smallest among those values. Call it M.
3) When all nodes in lstpNodes have been visited, the M-th last element in the stack is the LCA.

void Visit (CNode* pNode, const list <CNode*> lstpNodes, const CStack &Stack, unsigned &uFoundNodes, unsigned &uLCADepth)
{
	if (!std::find (lstpNodes.begin (), lstpNodes.end (), pNode))
		return false;

	uFoundNodes++;
	uLCADepth = min (uLCADepth, Stack.size () - 1 /* depth of parent */);
}

CNode* LCAOfNNodes (CNode* pRoot, const list <CNode*> lstpNodes)
{
	CStack Stack;
	CNode* pNode = pRoot, pLastVisited = NULL;
	unsigned uFoundNodes = 0, uLCADepth = (unsigned) -1;
	
	while (pNode)
	{
		while (pNode)
		{
			Stack.Push (pNode);
			pNode = pNode->pLeft;
		}
		
		while (!pNode)
		{
			pNode = Stack.Top ();
			if (pNode->pRight == NULL || pNode->pRight == pLastVisited)
			{
				Stack.Pop ();
				Visit (pNode, lstpNodes, Stack, uFoundNodes, uLCADepth);
				
				if (uFoundNodes == lstpNodes.size ())
				{
					while (iLCADepth > (Stack.size ()-1))
						Stack.Pop ();
					return Stack.Top ();
				}
				
				pLastVisited = pNode;
				pNode = NULL;
				continue;
			}
			
			pNode = pNode->pRight
		}
	}
	
	return NULL;
}

public TreeNode findLca(TreeNode root, List<TreeNode> nodes) {
        if (nodes.size() == 0) {
            return null;
        }

        VisitResult result = visitNode(root, nodes);
        return result.lcaNode;
    }

    private VisitResult visitNode(TreeNode node, List<TreeNode> nodes) {
        if (node == null) {
            return new VisitResult();
        }

        VisitResult leftResult = visitNode(node.left, nodes);
        if (leftResult.lcaNode != null) {
            return leftResult;
        }

        VisitResult rightResult = visitNode(node.right, nodes);
        if (rightResult.lcaNode != null) {
            return rightResult;
        }

        VisitResult result = new VisitResult();
        result.foundNodes = leftResult.foundNodes + rightResult.foundNodes;
        if (result.foundNodes == nodes.size()) {
            result.lcaNode = node;
        } else if (nodes.contains(node)) {
            result.foundNodes++;
        }
        return result;
    }

    private class VisitResult {

        int foundNodes = 0;
        TreeNode lcaNode = null;
    }

public int findLCA(Node root, List<Node> nodes){
       int lca = root.value;
       if(nodes != null && !nodes.isEmpty()){
           //Define paths from the root to each node
           List<List<Integer>> pathsToRoot = LCALib.buildPaths(nodes);
           //Get min path length
           int min = LCALib.getMinPath(pathsToRoot);
           //iterate paths limited to shortest path
           for(int i = 0; i < min; i++){
               //get path node at current level
               int lcaCandidate = pathsToRoot.get(0).get(i);
               int level = i;
               //evaluate candidate for all paths at same level, 
               //if true we are not diverged from the same path for all nodes.
               boolean matchedCandidate = LCALib.matchedCandidate(pathsToRoot, level, lcaCandidate);
               if(matchedCandidate){
                   //set new lca
                   lca = lcaCandidate;
               }
           }
       }
       return lca;
    }