non-recursive method for evaluating a binary tree representing an arithmetic expression

Question

As the subject states, I need to describe a method for evaluating a binary arithmetic expression tree without using recursion. No other details or instructions are given to me.

As far as my understanding of such things go, I need to simulate an inorder traversal of the tree. Assuming the availability of the ADT methods as outlined in my textbook, I have hasLeft(), hasRight(), left(), right(), isInternal(), and isExternal() methods. I need to ask my prof if I can make my own such method, but there's no parent() method to use so I can traverse back up the tree. Though, I do have a root() method.

Can somebody maybe point me in the right direction to figure out how to do this? I can't think of a way to do this without recursion, as I don't immediately have a way to jump back up the tree.

Answer 1

You may keep a stack of the nodes that has already been visited. Then you replace the recursive invocations by pushing a new node into the stack, and you pop a node from the stack where the recursive function would have returned.

Remember that when executing a recursive function, there is always an implicit stack that remembers what parameters were passed in each function call.