[Solved]: Binary tree traversals reversed

Problem Detail: 

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?

Asked By : Kevin

Answered By : Hendrik Jan

I would say you are right. If the post order of a tree is "left-recursion, right-recursion, root" then the reverse is "root, reverse-right-recursion, reverse-left-recursion", which is exactly what you propose. Technically the proof would state "by induction on the structure of the tree".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29449