Question

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top