I'm working on a project lifting assembler code to a AbstractSyntaxTree-like structures like these:

enter image description here

In order to be able to evaluate the final value of a tree given only leafes with constant values, I implemented an recursive approach: Each node class has its own value function. For all nodes except constants, it will query the value function of its children.

e.g. A add node has a value function which works like this:

self.children[0].value() + self.children[1].value()

This seems simple and stores Operation-Logic where it belongs: into operation nodes. The main problem is that these trees tend to be become very large and I fear an recursive approach might not be the best way here.

The most common operations ran on this tree are tree merging and optimization (transversal + modification). At the moment we use single-linked notes, since this serves the use cases in the best way.

Is there any iterative way of archiving this value evaluation? Any help appreciated.


A recursive function is only bad if it ends up repeating work and in this case it does not have too. A postorder traversal of the tree is what you want to do here, and the iterative solution exists, but is considerably more difficult to implemant. A post order traversal will only visit each node once, and you will not beat that for complexity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.