PCCST303 · Module 3: Trees and Graphs
Expression Trees
Infix, prefix, and postfix are different ways to write an expression as a flat string. An expression tree represents the same expression as a structure, and its shape connects directly to the tree traversals we've already seen.
Structure
Key Idea
In an expression tree, every operator becomes an internal node with its operands as children, and every operand becomes a leaf.
For (A + B) * C:
The * is the root because it's the last operation applied; + happens first, deeper in the tree, matching how (A + B) is evaluated before multiplying by C.
Traversals give the three notations
Key Idea
Traversing an expression tree with each of the three standard orders reproduces each of the three expression notations: preorder → prefix, inorder → infix, postorder → postfix.
For the tree above:
Preorder: * + A B C → prefix *+ABC
Inorder: (A+B)*C → infix (A+B)*C
Postorder: A B + C * → postfix AB+C*This isn't a coincidence: prefix notation writes the operator before its operands (root-left-right, same as preorder), and postfix writes the operator after (left-right-root, same as postorder). Infix, writing the operator between its operands, matches inorder for exactly the same reason.
Building the tree from postfix
The most common exam task isn't reading a tree, it's building one from a given postfix expression, using a stack, the same tool used to evaluate postfix expressions numerically. Here the stack holds tree nodes instead of numbers.
BUILD_EXPRESSION_TREE(POSTFIX)
1. Create empty stack S.
2. Scan postfix left to right.
3. If token is an operand:
Create a leaf node.
PUSH node onto S.
4. If token is an operator:
RIGHT = POP(S)
LEFT = POP(S)
Create operator node with LEFT and RIGHT as children.
PUSH node onto S.
5. ROOT = POP(S)
6. Return ROOT.Worked example: AB+C*
Read A: A is an operand. Push a leaf node A onto the stack. Stack now holds: A.
Read B: B is an operand. Push a leaf node B onto the stack. Stack now holds, bottom to top: A, B. A and B are still two separate nodes. They are not joined into a tree yet, that only happens when an operator arrives.
Read +: + is an operator. Pop twice: RIGHT = POP() = B, then LEFT = POP() = A. Combine LEFT and RIGHT under a new + node, then push that subtree back onto the stack. Stack now holds: (A+B).
Read C: C is an operand. Push a leaf node C onto the stack. Stack now holds, bottom to top: (A+B), C. The (A+B) subtree sits underneath, untouched. C waits on top for the next operator.
Read *: * is an operator. Pop twice: RIGHT = POP() = C, then LEFT = POP() = (A+B). Combine LEFT and RIGHT under a new * node, then push that subtree back onto the stack. Stack now holds: ((A+B)*C).
End of input: the stack now holds exactly one tree. ROOT = POP() = that tree, the root of the full expression.
Reading the tree back confirms it was built correctly. Its preorder gives * + A B C, the prefix form of the same expression. Prefix and postfix are just the same tree read in opposite directions.
Quick recall
- Operators are internal nodes, operands are leaves; the last-applied operation sits at the root.
- Preorder → prefix, inorder → infix, postorder → postfix, the traversal order matches where the operator appears relative to its operands in each notation.
- Building from postfix uses a stack of nodes: an operand pushes a leaf; an operator pops twice (first pop → right child, second pop → left child) and pushes the combined subtree.
- The final stack, after the whole postfix string is scanned, holds exactly one tree: the root of the full expression.