8.23 Expression Trees
Expression trees represent computations as tree structures.
8.23 Expression Trees
Expression trees represent computations as tree structures. Leaves usually hold operands, and internal nodes hold operators. This representation appears in compilers, interpreters, symbolic algebra systems, query engines, spreadsheet formulas, calculators, and optimization passes.
For example, the expression:
(3 + 4) * 5
can be represented as:
*
/ \\n + 5
/ \\n 3 4
The tree captures the structure of the computation. Parentheses, precedence, and evaluation order are no longer implicit in text. They are explicit in the shape of the tree.
Problem
You need to represent, evaluate, transform, or analyze expressions structurally rather than as raw strings.
Solution
Define a tree where each node is either:
- a literal value
- a variable
- an operator with children
For a simple arithmetic expression tree:
package main
import "fmt"
type Expr struct {
Op string
Value int
Left *Expr
Right *Expr
}
A leaf has an empty operator and stores a value.
func Literal(value int) *Expr {
return &Expr{
Value: value,
}
}
An operator node stores the operation and its operands.
func Binary(op string, left, right *Expr) *Expr {
return &Expr{
Op: op,
Left: left,
Right: right,
}
}
Build the expression:
expr := Binary(
"*",
Binary(
"+",
Literal(3),
Literal(4),
),
Literal(5),
)
This represents:
(3 + 4) * 5
Evaluating an Expression Tree
Evaluation is a postorder traversal.
First evaluate children.
Then apply the operator.
func Eval(expr *Expr) int {
if expr.Op == "" {
return expr.Value
}
left := Eval(expr.Left)
right := Eval(expr.Right)
switch expr.Op {
case "+":
return left + right
case "-":
return left - right
case "*":
return left * right
case "/":
return left / right
default:
panic("unknown operator: " + expr.Op)
}
}
Usage:
func main() {
expr := Binary(
"*",
Binary("+", Literal(3), Literal(4)),
Literal(5),
)
fmt.Println(Eval(expr))
}
Output:
35
The algorithm mirrors the tree structure exactly.
Discussion
An expression tree is useful because it separates syntax from semantics.
The string:
3 + 4 * 5
requires parsing rules to determine whether multiplication or addition happens first.
The tree:
+
/ \\n 3 *
/ \\n 4 5
has no ambiguity.
The structure itself defines the order.
This is why parsers usually produce abstract syntax trees before interpretation or compilation.
Variables
Real expressions often contain variables.
Extend the node type:
type ExprKind int
const (
LiteralKind ExprKind = iota
VariableKind
BinaryKind
)
type Expression struct {
Kind ExprKind
Value int
Name string
Op string
Left *Expression
Right *Expression
}
Evaluation now needs an environment.
func EvalWithEnv(
expr *Expression,
env map[string]int,
) int {
switch expr.Kind {
case LiteralKind:
return expr.Value
case VariableKind:
value, ok := env[expr.Name]
if !ok {
panic("undefined variable: " + expr.Name)
}
return value
case BinaryKind:
left := EvalWithEnv(expr.Left, env)
right := EvalWithEnv(expr.Right, env)
switch expr.Op {
case "+":
return left + right
case "-":
return left - right
case "*":
return left * right
case "/":
return left / right
default:
panic("unknown operator: " + expr.Op)
}
}
panic("invalid expression")
}
An expression such as:
x * (y + 2)
can now be evaluated under:
env := map[string]int{
"x": 3,
"y": 4,
}
Result:
18
Printing Expressions
Expression trees can be converted back into text.
A simple fully parenthesized printer:
func Print(expr *Expr) string {
if expr.Op == "" {
return fmt.Sprintf("%d", expr.Value)
}
return "(" +
Print(expr.Left) +
" " +
expr.Op +
" " +
Print(expr.Right) +
")"
}
For the earlier expression, it prints:
((3 + 4) * 5)
This format may contain more parentheses than necessary, but it is unambiguous.
Simplifying Expressions
Expression trees are easy to transform recursively.
Example rule:
x + 0 = x
Another rule:
x * 1 = x
Implementation:
func Simplify(expr *Expr) *Expr {
if expr == nil || expr.Op == "" {
return expr
}
left := Simplify(expr.Left)
right := Simplify(expr.Right)
if expr.Op == "+" &&
right.Op == "" &&
right.Value == 0 {
return left
}
if expr.Op == "+" &&
left.Op == "" &&
left.Value == 0 {
return right
}
if expr.Op == "*" &&
right.Op == "" &&
right.Value == 1 {
return left
}
if expr.Op == "*" &&
left.Op == "" &&
left.Value == 1 {
return right
}
return &Expr{
Op: expr.Op,
Left: left,
Right: right,
}
}
The transformation visits the tree bottom-up and rebuilds only what is needed.
Constant Folding
Compilers often simplify expressions at compile time.
Example:
(3 + 4) * x
can become:
7 * x
Constant folding is straightforward on expression trees:
func FoldConstants(expr *Expr) *Expr {
if expr == nil || expr.Op == "" {
return expr
}
left := FoldConstants(expr.Left)
right := FoldConstants(expr.Right)
if left.Op == "" && right.Op == "" {
return Literal(Eval(Binary(expr.Op, left, right)))
}
return &Expr{
Op: expr.Op,
Left: left,
Right: right,
}
}
This is one of the simplest examples of compiler optimization.
Expression Trees in Query Engines
SQL query planners also use expression trees.
A predicate such as:
price > 100 AND category = 'Books'
can be represented as:
AND
/ \\n > =
/ \ / \\nprice 100 category Books
This structure allows a query optimizer to:
- push filters closer to table scans
- reorder predicates
- simplify constant expressions
- detect indexable conditions
The same tree principles apply outside programming languages.
Expression Trees in Spreadsheets
A spreadsheet formula:
=A1 + SUM(B1:B10)
can be parsed into an expression tree.
The evaluation engine can then:
- resolve cell references
- compute dependencies
- cache results
- detect cycles
- recompute affected cells after updates
The tree representation makes dependencies explicit.
Expression Trees and ASTs
An expression tree is a specific kind of Abstract Syntax Tree.
An AST may represent a full program:
function declarations
statements
expressions
types
modules
An expression tree focuses on expression structure.
The underlying ideas remain the same:
- nodes represent syntax categories
- edges represent containment
- traversal drives analysis and transformation
Complexity Analysis
Let n be the number of nodes in the expression tree.
| Operation | Complexity |
|---|---|
| Evaluation | O(n) |
| Printing | O(n) |
| Simplification | O(n) |
| Constant folding | O(n) |
Memory depends on whether transformations mutate the tree or allocate a new one.
Immutable transformations often allocate O(n) new nodes in the worst case.
Common Mistakes
A common mistake is evaluating operators before children. Expression evaluation is naturally postorder.
Another mistake is treating raw strings as expressions for too long. Once parsing is complete, structural algorithms should operate on trees, not substrings.
A third mistake is ignoring operator arity. Unary operators, binary operators, function calls, and variadic operators need different node forms.
A fourth mistake is dropping parentheses during printing. A printer must preserve precedence or emit fully parenthesized output.
Finally, simplification rules must preserve semantics. A rule that works for integers may fail for floating-point arithmetic, overflow behavior, or division by zero.
Takeaway
Expression trees make computation structural. By representing literals, variables, and operators as nodes, they allow evaluation, printing, simplification, optimization, and dependency analysis to be implemented as tree traversals. This representation is foundational in compilers, interpreters, query engines, spreadsheets, calculators, and symbolic computation systems.