Simplifying expression trees

Expression Trees

Simplification

Mathematical Expressions

Computer Science

Algorithm Optimization

Simplifying expression trees

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Algorithms Data Structures Complexity & Performance

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

python

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

python

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):

python

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

python

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:

python

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:

csharp

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

DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course

Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Simplifying expression trees

Data Structures & Algorithms practice on Codemia

Introduction

Expression Tree Representation

Simplification Rules

Simplification Algorithm

Examples

Multi-Pass Simplification

Compiler Optimization Context

C# / LINQ Expression Trees

Common Pitfalls

Summary

Related reading

DSA Fundamentals

Track what you have practised

Data Structures & Algorithms practice on Codemia