You're correct in noting this is not a trivial problem.
The classical way that compilers handle it is a Directed Acyclic Graph (DAG) representation of the expression. The DAG is built in the same manner as the abstract syntax tree (and can be built by traversing the AST - perhaps a job for the expression visitor; I don't know much of C# libraries), except that a dictionary of previously emitted subgraphs is maintained. Before generating any given node type with given children, the dictionary is consulted to see if one already exists. Only if this check fails is a new one created, then added to the dictionary.
Since now a node may descend from multiple parents, the result is a DAG.
Then the DAG is traversed depth first to generate code. Since common sub-expressions are now represented by a single node, the value is only computed once and stored in a temp for other expressions emitted later in the code generation to use. If the original code contains assignments, this phase gets complicated. Since your trees are side-effect free, the DAG ought to be the most straightforward way to solve your problem.
As I recall, the coverage of DAGs in the Dragon book is particularly nice.
As others have noted, if your trees will ultimately be compiled by an existing compiler, it's kind of futile to redo what's already there.
Addition
I had some Java code laying around from a student project (I teach) so hacked up a little example of how this works. It's too long to post, but see the Gist here.
Running it on your input prints the DAG below. The numbers in parens are (unique id, DAG parent count). The parent count is needed to decide when to compute the local temp variables and when to just use the expression for a node.
Binary OR (27,1)
lhs:
Binary OR (19,1)
lhs:
Binary GREATER (9,1)
lhs:
Binary ADD (7,2)
lhs:
Binary MULTIPLY (3,2)
lhs:
Id 'Bar' (1,1)
rhs:
Number 5 (2,1)
rhs:
Binary MULTIPLY (6,1)
lhs:
Id 'Baz' (4,1)
rhs:
Number 2 (5,1)
rhs:
Number 7 (8,1)
rhs:
Binary LESS (18,1)
lhs:
ref to Binary ADD (7,2)
rhs:
Number 3 (17,2)
rhs:
Binary EQUALS (26,1)
lhs:
Binary ADD (24,1)
lhs:
ref to Binary MULTIPLY (3,2)
rhs:
ref to Number 3 (17,2)
rhs:
Id 'Xyz' (25,1)
Then it generates this code:
t3 = (Bar) * (5);
t7 = (t3) + ((Baz) * (2));
return (((t7) > (7)) || ((t7) < (3))) || (((t3) + (3)) == (Xyz));
You can see that the temp var numbers correspond to DAG nodes. You could make the code generator more complex to get rid of the unnecessary parentheses, but I'll leave that for others.