Introduction
An expression tree is a binary tree where internal nodes are operators (+, -, *, /) and leaf nodes are operands (numbers or variables). Simplifying an expression tree means applying algebraic rules to reduce it to a simpler equivalent form — constant folding (computing 3 + 5 → 8), identity removal (eliminating x * 1 → x), and algebraic rewrites (reducing x - x → 0). This is a core optimization in compilers, computer algebra systems, and symbolic math libraries.
Expression Tree Representation
1class Expr:
2 pass
3
4class Num(Expr):
5 def __init__(self, value):
6 self.value = value
7 def __repr__(self):
8 return str(self.value)
9
10class Var(Expr):
11 def __init__(self, name):
12 self.name = name
13 def __repr__(self):
14 return self.name
15
16class BinOp(Expr):
17 def __init__(self, op, left, right):
18 self.op = op
19 self.left = left
20 self.right = right
21 def __repr__(self):
22 return f"({self.left} {self.op} {self.right})"
The expression (3 + x) * 2 is represented as:
1 *
2 / \
3 + 2
4 / \
5 3 x
tree = BinOp('*', BinOp('+', Num(3), Var('x')), Num(2))
print(tree) # ((3 + x) * 2)
Simplification Rules
The core algebraic identities to apply:
| Rule | Before | After |
| Constant folding | 3 + 5 | 8 |
| Additive identity | x + 0 or 0 + x | x |
| Multiplicative identity | x * 1 or 1 * x | x |
| Multiplication by zero | x * 0 or 0 * x | 0 |
| Self-subtraction | x - x | 0 |
| Self-division | x / x | 1 |
| Division identity | x / 1 | x |
| Double negation | --x | x |
| Subtraction of zero | x - 0 | x |
Simplification Algorithm
Apply rules recursively, bottom-up (simplify children first, then apply rules to the result):
1def simplify(node):
2 if isinstance(node, (Num, Var)):
3 return node
4
5 # Recursively simplify children first
6 left = simplify(node.left)
7 right = simplify(node.right)
8
9 # Constant folding — both children are numbers
10 if isinstance(left, Num) and isinstance(right, Num):
11 if node.op == '+': return Num(left.value + right.value)
12 if node.op == '-': return Num(left.value - right.value)
13 if node.op == '*': return Num(left.value * right.value)
14 if node.op == '/' and right.value != 0:
15 return Num(left.value / right.value)
16
17 # Identity rules for addition
18 if node.op == '+':
19 if isinstance(left, Num) and left.value == 0: return right # 0 + x → x
20 if isinstance(right, Num) and right.value == 0: return left # x + 0 → x
21
22 # Identity rules for subtraction
23 if node.op == '-':
24 if isinstance(right, Num) and right.value == 0: return left # x - 0 → x
25 if equal(left, right): return Num(0) # x - x → 0
26
27 # Identity rules for multiplication
28 if node.op == '*':
29 if isinstance(left, Num) and left.value == 0: return Num(0) # 0 * x → 0
30 if isinstance(right, Num) and right.value == 0: return Num(0) # x * 0 → 0
31 if isinstance(left, Num) and left.value == 1: return right # 1 * x → x
32 if isinstance(right, Num) and right.value == 1: return left # x * 1 → x
33
34 # Identity rules for division
35 if node.op == '/':
36 if isinstance(right, Num) and right.value == 1: return left # x / 1 → x
37 if equal(left, right): return Num(1) # x / x → 1
38
39 return BinOp(node.op, left, right)
40
41def equal(a, b):
42 """Structural equality check."""
43 if isinstance(a, Num) and isinstance(b, Num):
44 return a.value == b.value
45 if isinstance(a, Var) and isinstance(b, Var):
46 return a.name == b.name
47 if isinstance(a, BinOp) and isinstance(b, BinOp):
48 return a.op == b.op and equal(a.left, b.left) and equal(a.right, b.right)
49 return False
Examples
1# Constant folding: (3 + 5) * 2 → 16
2tree = BinOp('*', BinOp('+', Num(3), Num(5)), Num(2))
3print(simplify(tree)) # 16
4
5# Identity removal: x * 1 + 0 → x
6tree = BinOp('+', BinOp('*', Var('x'), Num(1)), Num(0))
7print(simplify(tree)) # x
8
9# Self-subtraction: (a + b) - (a + b) → 0
10tree = BinOp('-',
11 BinOp('+', Var('a'), Var('b')),
12 BinOp('+', Var('a'), Var('b')))
13print(simplify(tree)) # 0
14
15# Mixed: (x * 0) + (y * 1) → y
16tree = BinOp('+', BinOp('*', Var('x'), Num(0)), BinOp('*', Var('y'), Num(1)))
17print(simplify(tree)) # y
Multi-Pass Simplification
One pass may not fully simplify an expression. Apply simplification repeatedly until the tree stops changing:
1def fully_simplify(node):
2 prev = None
3 current = node
4 while not equal(prev, current) if prev else True:
5 prev = current
6 current = simplify(current)
7 return current
8
9# (x + 0) * 1 → first pass: x * 1 → second pass: x
10tree = BinOp('*', BinOp('+', Var('x'), Num(0)), Num(1))
11print(fully_simplify(tree)) # x
Compiler Optimization Context
Compilers apply expression tree simplification as part of their optimization passes:
1Source code: y = (x * 1) + (0 * z) - 0
2Parse tree: Sub(Add(Mul(x, 1), Mul(0, z)), 0)
3
4After simplification:
5 Mul(x, 1) → x
6 Mul(0, z) → 0
7 Add(x, 0) → x
8 Sub(x, 0) → x
9
10Optimized: y = x (single register copy instead of 3 operations)
GCC and LLVM perform these optimizations on their intermediate representations (IR), eliminating redundant arithmetic instructions.
C# / LINQ Expression Trees
In C#, System.Linq.Expressions provides expression trees for runtime code generation:
1using System.Linq.Expressions;
2
3// Build: x => x * 1 + 0
4var param = Expression.Parameter(typeof(double), "x");
5var body = Expression.Add(
6 Expression.Multiply(param, Expression.Constant(1.0)),
7 Expression.Constant(0.0));
8var expr = Expression.Lambda<Func<double, double>>(body, param);
9
10// The C# compiler does not simplify expression trees automatically.
11// Libraries like MetaLinq or custom visitors can simplify them.
Common Pitfalls
Floating-point precision: x - x is not always exactly 0 for floats. 0.1 + 0.2 - 0.3 ≈ 5.5e-17, not 0. Use tolerance-based comparison for constant folding with floats.
Division by zero: x / x → 1 is only valid when x ≠ 0. A robust simplifier must track constraints or leave x / x unsimplified when x could be zero.
Non-commutative operations: Subtraction and division are not commutative. a - b ≠ b - a. Do not apply commutativity rules to these operators.
Infinite loops: Without a convergence check, simplification can oscillate between equivalent forms. The fully_simplify approach with structural equality prevents this.
Missing rules: A minimal simplifier only handles basic identities. Real computer algebra systems (SymPy, Mathematica) apply hundreds of rules including distribution, factoring, trigonometric identities, and logarithm laws.
Summary
Expression trees represent mathematical expressions as binary trees (operators at internal nodes, operands at leaves)
Simplification applies algebraic rules bottom-up: constant folding, identity removal, zero multiplication
Use recursive simplification on children first, then apply rules to the parent node
Multiple passes may be needed — repeat until the tree stops changing
Structural equality checks determine when two subtrees are identical
Compilers use these techniques to eliminate redundant arithmetic in generated code
