non-recursive method for evaluating a binary tree representing an arithmetic expression
algorithm, binary-tree, java
Solution
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.
Problem
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.