I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search_2, which I also copied below.
What confuses me most is that
I find the non-recursive implementations using stacks are not easy to understand.
It also seems to me that the three non-recursive implementations are ad hoc on each own, and I can't find if there is a way to unify their creations.
Can they be reformuated and/or created from the recursive implementations in some unified way, so that I can write them out by just looking at the recursive implementations?
Since a compiler can implement recursions using stacks, I believe it is possible to do that.
Usually, I replace a recursive algorithm by an iterative algorithm by pushing the parameters that would normally be passed to the recursive function onto a stack. In fact, you are replacing the program stack by one of your own.
Stack<Object> stack; stack.push(first_object); while( !stack.isEmpty() ) { // Do something my_object = stack.pop(); // Push other objects on the stack. }
Note: if you have more than one recursive call inside and you want to preserve the order of the calls, you have to add them in the reverse order to the stack:
foo(first); foo(second);
has to be replaced by
stack.push(second); stack.push(first);
In the idea of the reply, the non-recursive implementation of preorder is easier to understand than the non-recursive implemenations of the other two. The non-recursive implemenations of the other two don't seem to follow the idea at least closely, and can they be written to follow the idea closely?
Thanks.
Note the implementations from Wikipedia are
Pre-order
preorder(node) if (node = null) return visit(node) preorder(node.left) preorder(node.right) iterativePreorder(node) if (node = null) return s ← empty stack s.push(node) while (not s.isEmpty()) node ← s.pop() visit(node) if (node.right ≠ null) s.push(node.right) if (node.left ≠ null) s.push(node.left)
In-order
inorder(node) if (node = null) return inorder(node.left) visit(node) inorder(node.right) iterativeInorder(node) s ← empty stack while (not s.isEmpty() or node ≠ null) if (node ≠ null) s.push(node) node ← node.left else node ← s.pop() visit(node) node ← node.right
Post-order
postorder(node) if (node = null) return postorder(node.left) postorder(node.right) visit(node) iterativePostorder(node) s ← empty stack lastNodeVisited ← null while (not s.isEmpty() or node ≠ null) if (node ≠ null) s.push(node) node ← node.left else peekNode ← s.peek() // if right child exists and traversing node // from left child, then move right if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right) node ← peekNode.right else visit(peekNode) lastNodeVisited ← s.pop()