Many Boolean functions have short representations by OBDDs (ordered
binary decision diagrams) if appropriate variable orderings are used.
For tree-like circuits, which may contain EXOR-gates, it is proved
that some depth first traversal leads to an optimal variable ordering.
Moreover, an optimal variable ordering and the resulting OBDD
can be computed in time linear in the number of variables and the size of
the OBDD, respectively.
Upper and lower bounds on the OBDD size of the functions
representable by tree-like circuits are derived.
For, e. g., 1024 inputs, we show that all tree-like circuits have
OBDDs of size at 5349 and we give an example of a tree-like circuit
requiring an OBDD of size 5152.