Module 6 · Interactive topic

Expression Trees

Operators inside, operands outside

An expression such as a + b * c becomes a binary tree: operators are internal nodes and operands are leaves, so the shape of the tree already says what is calculated first. Watch it built with a stack from infix, postfix or prefix, read it back with the three traversals, and evaluate it.

  • Operanda number or letter — a leaf
  • Operator+ − * / ^ — an internal node
  • Postfixa b c * + (operator after)
  • Prefix+ a * b c (operator before)
Expression Tree Ready
nodes 0
height 0
leaves 0
  • Current
  • Joined next
  • Done
  • New

Ready

Comparisons 0 Shifts 0
Ready

Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode

How it works

Every operation, in plain steps

These are exactly the steps the visualizer animates.

Operators inside, operands outside

An expression tree is a binary tree where every INTERNAL node is an operator (+ − * / ^) and every LEAF is an operand (a number or a letter). The shape of the tree already says what must be calculated first — no brackets and no priority rules are needed to read it. To build one we keep a STACK of trees: operands become one-node trees, and an operator joins the top two.

struct Node {
    char data;             // an operator (+ - * / ^) or an operand (a, b, 3 ...)
    struct Node *left;     // the left operand (a subtree)
    struct Node *right;    // the right operand (a subtree)
};

// a + b * c        operators are internal nodes, operands are leaves
//
//       +
//      / \
//     a   *          b * c is calculated first because it is deeper
//        / \
//       b   c

From postfix

  1. Read the expression from LEFT to right.
  2. An operand becomes a one-node tree pushed on the stack.
  3. An operator pops two trees: the FIRST pop is its right child, the second its left child.
  4. Push the new tree back. At the end exactly one tree is left.

From prefix

  1. The operator comes BEFORE its operands, so read from RIGHT to left.
  2. An operand becomes a one-node tree pushed on the stack.
  3. An operator pops two trees: the FIRST pop is its LEFT child, the second its right child.
  4. Push the new tree back. At the end exactly one tree is left.

From infix

  1. Use two stacks: operators, and trees.
  2. Operands go straight to the tree stack; "(" waits on the operator stack.
  3. Before an operator waits, finish every operator on top with a higher (or equal) priority.
  4. ")" finishes everything back to its "(". At the end finish what is left.

Priority and order

  1. ^ goes first, then * and /, then + and −.
  2. Equal priority: left to right, so a − b − c = (a − b) − c.
  3. The exception is ^ , which goes right to left: a ^ b ^ c = a ^ (b ^ c).
  4. Brackets override all of it.

Read the tree back

  1. Inorder (left, node, right) gives the INFIX expression.
  2. Preorder (node, left, right) gives the PREFIX expression.
  3. Postorder (left, right, node) gives the POSTFIX expression.
  4. Inorder loses the brackets — the tree itself remembers the order.

Evaluate the tree

  1. A leaf is just its value (a letter needs a value).
  2. An operator waits until both subtrees have values.
  3. Then it applies itself: left (operator) right.
  4. This is a postorder walk: the root holds the answer.
Algorithm

Pseudocode

Language-independent steps. The visualizer shows the same logic in C, Python and Java.

1 BUILD-POSTFIX(tokens)
2 stack ← empty stack of trees
3 for each token t from left to right
4 if t is an operand then push(stack, new Node(t))
5 else
6 node ← new Node(t)
7 node.right ← pop(stack)
8 node.left ← pop(stack)
9 push(stack, node)
10 return pop(stack)
Complexity

How fast is each operation?

n = number of tokens (and nodes), h = height. Every token is pushed and popped at most once, so building is O(n).

Operation Best Average Worst Speed
Build from postfix / prefix O(n) O(n) O(n) Grows with n
Build from infix O(n) O(n) O(n) Grows with n
Inorder / preorder / postorder O(n) O(n) O(n) Grows with n
Evaluate O(n) O(n) O(n) Grows with n

The three notations

Infix Postfix Prefix
a + b * c a + b * c a b c * + + a * b c
Operator goes between its operands after its operands before its operands
Brackets / priorities needed? Yes No No
Read from the tree with Inorder Postorder Preorder
Build the tree with Two stacks (operators + trees) One stack, scanning left to right One stack, scanning right to left
Used by People, school maths Calculators (RPN), compilers Lisp, some compilers

Operator priority

Operator Priority Same priority is done
^ 3 (highest) right to left: a ^ b ^ c = a ^ (b ^ c)
* / 2 left to right: a / b * c = (a / b) * c
+ − 1 (lowest) left to right: a − b − c = (a − b) − c

Brackets always win: what is inside them is finished first.

Practice

Check your understanding

Answer each question — you will see the explanation straight away.

0 / 8 correct
Question 1

In an expression tree, where are the operands (numbers and letters)?

Question 2

The postfix expression a b c * + gives a tree. What is its root?

Question 3

Building from postfix, an operator pops two trees. The FIRST tree popped becomes its…

Question 4

Which traversal of an expression tree gives the POSTFIX expression?

Question 5

Why is a prefix expression read from RIGHT to left when building the tree?

Question 6

Building from infix a + b * c, why is * combined before +?

Question 7

In a ^ b ^ c, which node is the right child of the root?

Question 8

When can the operator at a node of an expression tree be applied?

Assessment

Trees quiz

Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.

Create a free account →
← Previous topic Variants of the Binary Tree Next topic → Huffman Trees