Expression tree and traversals

An expression tree is a binary tree whose leaves are operands and whose internal nodes are operators. The expression is (a + (b*c) − d + (e*f/g)). Operators * and / have higher precedence than + and −, and operators of equal precedence are evaluated left to right. So it groups as:

((a + (bc)) − d) + ((ef) / g)

Expression tree

                  +
             /         \
            -           /
          /   \        /  \
         +     d      *    g
        / \          / \
       a   *        e   f
          / \
         b   c

Pre-order traversal (root, left, right) gives prefix form

+ - + a * b c d / * e f g

In-order traversal (left, root, right) gives infix form

a + b * c - d + e * f / g

(Parentheses are needed to show the grouping: ((a+(bc))−d)+((ef)/g).)

For comparison, post-order gives a b c * + d - e f * g / +.

Traversal steps (pre-order)

Visit +(root) → left - → its left + → a → * → b, c → d → right / → * → e, f → g.