1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Raphael Aug 28 '14 at 12:43
  • $\begingroup$ 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. $\endgroup$ – kmantel Aug 30 '14 at 4:20
2
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.