# Binary tree traversals reversed

Am I correct in saying that

traverse(node):
if node is null, return
print node
traverse(node's right subtree)
traverse(node's left subtree)


would produce output that is the reverse of post-order traversal?

post-order(node):
if node is null, return
post-order(node's left subtree)
post-order(node's right subtree)
print node


I am mostly interested because if this is true, it greatly simplifies the iterative method for post-order traversal. It "feels" right with a hand-wavey explanation - and with testing on some trees - but how would I prove it?

• What have you tried towards proving that your algorithm is correct and where did you get stuck? (Also, I don't see how this simplifies anything.) – Raphael Aug 28 '14 at 12:43
• See leetcode.com/2010/10/binary-tree-post-order-traversal.html regarding simplification. I thought of using induction, with a base case of a single leaf and the main logical step as "if the left and right subtrees are ordered properly...", but I'm not convinced it is sound. – kmantel Aug 30 '14 at 4:20