Data Structures - Expression Tree

<< Previous

Next >>

Expression Tree is used to represent expressions. There are different types of expression formats:

Fig 1.Expression Tree

  • Prefix expression
  • Infix expression and
  • Postfix expression

Expression Tree is a special kind of binary tree with the following properties:

  • Each leaf is an operand.
  • The root and internal nodes are operators.
  • Subtrees are subexpressions with the root being an operator.

Traversal Techniques

There are 3 standard traversal techniques to represent the 3 different expression formats.

Inorder Traversal

We can produce an infix expression by

  • recursively printing out the left expression,
  • then printing out the root, and
  • recursively printing out right expression.

Postorder Traversal

The postfix expression can be evaluated by

  • recursively printing out the left expression,
  • right expression and
  • then root

Preorder Traversal

We can also evaluate prefix expression by:

  • printing out the root and
  • then recursively print out the left and
  • right expression.

If we apply all these strategies to the sample tree above, the outputs are:

  • Infix expression: (a+(b*c))+(d*(e + f))
  • Postfix Expression: a b c * + d e f + * +
  • Prefix Expression: + + a * b c * d + e f

Construction of Expression Tree

We consider that a postfix expression is given as an input for constructing an expression tree. Following are the step to construct an expression tree:

  1. Read one symbol at a time from the postfix expression.
  2. Check if the symbol is an operand or operator.
  3. If the symbol is an operand, create a one node tree and pushed a pointer onto a stack
  4. If the symbol is an operator, pop two pointer from the stack namely T1 & T2 and form a new tree with root as the operator, T1 & T2 as a left and right child
  5. A pointer to this new tree is pushed onto the stack


The input is:

a b + c *

The first two symbols are operands, we create one-node tree and push a pointer to them onto the stack.

Next, read a'+' symbol, so two pointers to tree are popped,a new tree is formed and push a pointer to it onto the stack.

Next, 'c' is read, we create one node tree and push a pointer to it onto the stack.

Finally, the last symbol is read ' * ', we pop two tree pointers and form a new tree with a, ' * ' as root, and a pointer to the final tree remains on the stack.

<< Previous

Next >>

Learn about Operating System © 2017