  We introduce and study the weakly single-crossing domain on trees which is a
generalization of the well-studied single-crossing domain in social choice
theory. We design a polynomial-time algorithm for recognizing preference
profiles which belong to this domain. We then develop an efficient elicitation
algorithm for this domain which works even if the preferences can be accessed
only sequentially and the underlying single-crossing tree structure is not
known beforehand. We also prove matching lower bound on the query complexity of
our elicitation algorithm when the number of voters is large compared to the
number of candidates. We also prove a lower bound of $\Omega(m^2\log n)$ on the
number of queries that any algorithm needs to ask to elicit single crossing
profile when random queries are allowed. This resolves an open question in an
earlier paper and proves optimality of their preference elicitation algorithm
when random queries are allowed.
