Algorithm for converting a binary tree to a postfix mathematical expression?

Question

I have a binary tree for mathematical expression (infix), I want to directly convert this TREE to postfix (Stack), can any body offer an algorithm?

Answer 1

What you are looking for is called post-order tree traversal :

postorder(node)
  if node.left  ≠ null then postorder(node.left)
  if node.right ≠ null then postorder(node.right)
  print node.value

Answer 2

Easy, every node (left, right, data).

Start with the first node. execute the algorithm for the left subtree, if available, and then execute the algorithm for the right subtree and then print the data.

TreeNode = ([TreeNode], Data, [TreeNode])

TreeToPostfix: [TreeNode] -> Data*
TreeToPostfix(nil) = []
TreeToPostfix((left, data, right)) ==
  TreeToPostfix(left) ++ TreeToPostfix(right) ++ Data

For example:

              +
            /   \
           *     -
          / \   / \
         2   3 4   5

Produces: 2 3 * 4 5 - +