Find rooted sub-tree containing predefined set of values

Question

Given a tree of nodes find a rooted sub-tree that contains a set of predefined values. The nodes in the tree are unique but their associated values may be repeated.

Ideally the most shallow sub-tree is returned. The sub-tree may also be returned simply as an array of nodes (or their unique IDs).

Here are several atomic test cases with the ideal resulting sub-tree:

#1 [A, A, B, C]

        A1           Answer:      A1
      / | \                      /  \
    B1  D1 C1                   B1   C1
   /  \      \                 /
  A2   B2     B3              A2

#2 [A, B, B, A]

      A1              Answer(s):        A1            A1         A1         the first solution is preferred
     /  \                              / \           /            \         as it is most shallow
    B1   B2                           B1  B2        B1             B2
   /  \    \                         /             / \              \
  A2   B3   B4                      A2           A2   B3             B4
              \                                                       \
               A3                                                      A3

#3 [A, A, B, C]

      A1               Answer: Not possible as only one B can be matched
     /  \
    B1   B2
   /       \
  A2        C1

#4 [B, B]

     A1               Answer: Not possible as the root 'A' is not in the set
    /  \
   B1   B2

My approach was broken into two steps:

1. Breadth-first scan until all nodes in the set are found returning a tree that definitely contains the desired sub-tree.
2. Use backtracking to search the resulting sub-tree (essentially all permutations of the sub-tree) to find the exact nodes that satisfy the set.

However, this solution is not very efficient. It seems like I should be able to find the desired sub-tree simply by using a modified breadth-first search. I've also been unable to make this work in practice.