# Simplify logical expression represented as binary tree

I implemented logical expressions using a binary tree in C++. Now I want to be able to simplify such an expression using rules like e.g.

$X\oplus&space;X&space;=&space;false$

but have issues with the commutativity. Assuming the expression is

$true&space;\oplus&space;a&space;\oplus&space;true&space;\oplus&space;b$

then the tree would look like this:

       xor
/\
xor b
/\
xor true
/\
true a


The expression can be simplified:

$true&space;\oplus&space;true&space;\oplus&space;a&space;\oplus&space;b&space;=&space;false&space;\oplus&space;a&space;\oplus&space;b&space;=&space;a&space;\oplus&space;b$

but I don't know how to apply the above rule to this tree since it is never directly applicable to one of the subtrees. Is there a better way than having to rotate the tree in all possible orders?

• Convert to list, sort (so that the same variables/values are grouped together), apply rules, convert back to binary tree. – Dmitry Aug 21 '20 at 18:15
• @Dmitry There's no need to sort, using a hashmap you can do it in $O(n)$ by only keeping track of the parity of each element. – orlp Aug 21 '20 at 21:45
• @twinrix another idea is to allow ($\lnot a$) in your tree. That way you could use the reduction $true \oplus x = x \oplus true = \lnot x$ ( and ofc $false \oplus x = x$). You would end up with: xor(true, a) => not(a), xor(not(a),true) => a, xor(a,b) as final result. Other rules are $x\oplus \lnot x = true$, $x \oplus x = false$. – plshelp Aug 23 '20 at 0:21