Reconstructing a tree from separator queries
No.  The following simple adversary strategy implies that any algorithm to reconstruct an $n$-node tree requires at least $\binom{n-1}{2} = n(n-1)/2$ "betweenness" queries.

Arbitrarily label the nodes $0,1,2,\dots,n-1$.  The adversary answers all queries as though the tree is a star with vertex $0$ in the center; think of $0$ as the root and the other nodes as its children.

Between?(a,x,b)
    if x=0 return TRUE else return FALSE


Now suppose the algorithm halts after performing less than $n(n-1)/2$ queries.  Then there must be two vertices $y$ and $z$, neither equal to zero, such that the algorithm has not queried any permutation of the triple $(0,y,z)$.  If the algorithm claims that the tree is not a star with center $0$, the adversary reveals its input, proving the algorithm wrong.  The adversary then reveals that $x$ is actually the only child of $y$, proving the algorithm wrong again.

Update: Oops, just noticed the degree constraint.  Fortunately, this is not a major hurdle.  Replace node $0$ with your favorite binary tree, with the other $n-1$ nodes as leaves in some unknown order, and then reveal this subtree to the reconstruction algorithm.  Reconstructing the resulting $(2n-3)$-node binary tree still requires at least $n(n-1)/2$ queries.  Equivalently, reconstructing an $m$-node binary tree requires at least $(m+3)(m+2)/8$ queries.  (I'm sure a more subtle construction would improve the constant.)  As Jagadish points out, this generalization doesn't work; queries about internal nodes in the tree impose an ordering on the leaves, which reduced the number of necessary queries.