How to put postfix expressions in a binary tree?

algorithm tree postfix-notation
Mudasir Soomro picture Mudasir Soomro · Dec 4, 2011 · Viewed 16.3k times · Source

so i have a binary tree and a postfix expression "6 2 * 3 /" what is the algo to put it in a tree? like,

          [/]
          / \
        [*]  [3]
        / \
      [6] [2]

Answer

Kevin Reid picture Kevin Reid · Dec 4, 2011

To construct a tree from the expression, pretend you are evaluating it directly but construct trees instead of calculating numbers. (This trick works for many more things than postfix expressions.)

Algorithm: Have a stack to store intermediate values (which are trees), and examine each token from left to right:

  • If it is a number, turn it into a leaf node and push it on the stack.
  • If it is an operator, pop two items from the stack, construct an operator node with those children, and push the new node on the stack.

At the end, if the expression is properly formed, then you should have exactly one tree on the stack which is the entire expression in tree form.

Related questions

What is the difference between tree depth and height?

This is a simple question from algorithms theory. The difference between them is that in one case you count number of nodes and in other number of edges on the shortest path between root and concrete node. Which is which?

Read More
What is the most efficient/elegant way to parse a flat table into a tree?

Assume you have a flat table that stores an ordered tree hierarchy: Id Name ParentId Order 1 'Node 1' 0 10 2 'Node 1.1' 1 10 3 'Node 2' 0 20 4 'Node 1.1.1' 2 10 5 'Node 2.1' 3 10 6 'Node 1.2' 1 20 Here's a diagram, where we have [id] Name. Root node 0 is fictional. [0] …

Read More
Non-recursive depth first search algorithm

I am looking for a non-recursive depth first search algorithm for a non-binary tree. Any help is very much appreciated.

Read More