Tree: Postorder Traversal

  • + 9 comments

    OK, I see everyone is writing this:

    def postOrder(root):
        if root:
            postOrder(root.left)
            postOrder(root.right)
            print(root.data, end=' ')
    

    But that seems wasteful to me, because you're calling the function first, then checking to see if there's anything to call it on. So for every leaf node you're calling the function twice for no reason, and for every node with only one child you're calling it once for no reason. Why not check before calling, like this:

    def postOrder(root):
        if root.left:
            postOrder(root.left)
        if root.right:
            postOrder(root.right)
        print(root.data, end=' ')
    

    Can anyone tell me why the first way is preferable?