Algorithm for converting Binary tree to post-fix mathematical expression?

Question

I have a Binary tree for a mathematical expression(infix), i want to convert directly this TREE to a postfix(Stack) can any body suggest the algorithm?

Answer 1

Easy, each node is (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 - +

Answer 2

What you’re searching for is known as 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