Iterative “post order” tree traversal [closed]

Question

I wanted to get feedback on the correctness and efficiency of this post order traversal routine that my wife and I find really easy to grasp.

def postOrderTraversal(root: TreeNode):
  curr = root
  stack = []

  while stack or curr:
    if curr is None:
      if stack[-1].right is None or popped == stack[-1].right:
        popped = stack.pop()
        print(popped.val)
      else:
        curr = stack[-1].right
    else:
      stack.append(curr)
      curr = curr.left

Answer 1

Congratulations on finding code you enjoy!

This appears to be walking through a binary tree you have defined (or possibly from toytree?). Walking through this with an explicit stack is one way of thinking of the problem, and the code can be a good learning experience.

An alternate method would be to use the Python's recursion system, where you make code vaguely like:

   def walk(tree):
        if tree is not None:   # ignore walking into an empty node
            walk(tree.left)
            walk(tree.right)
            print(tree.val)

It takes a a little brain stretching to see these as equivalent. As an exercise you should explore making the function a generator. That is, would call it as:

  for value in tree.walk():
      print(value)

To do this, you need to replace a print with a yield, and a recursive call with a yield from. Try it: it does a different stretch on the brain.

As far as efficiency, you need to use the the timeit module to see what does run fast. In general, tree structures with a single value do poorly for really large numbers because memory access is a bit slow. However, profiling is necessary for optimizing by less than factors of n (the size of the tree). Orders of magnitude can be judged by eye and logic while unexpected internals might double the speed of some code.

You might notice that your code will currently fail on being passed an empty tree (root=None), as popped will be checked before it is assigned. I am not sure why you are checking if popped equals the right node.

Keep hacking! Keep notes.

Answer 2

PEP-8

As commented by greybeard, the PEP-8 guidelines for Python suggest using CapWords for class names, and snake_case for variables and method names. So postOrderTraversal should be post_order_traversal

Type Hints

Your code is incomplete, which makes it more difficult to review. Clearly, you have defined the TreeNode elsewhere, or your code would not run. You should include that code in your question post. (But don’t change it now that there have been answers posted to your question; your change would just be rolled back. In future questions, include all referenced code, including import statements and type definitions.)

You are only half using type hints. You indicate that postOrderTraversal takes a TreeNode as an input parameter, but not specified what it returns. It doesn’t return anything, which should be indicated with -> None. Eg)

def postOrderTraversal(root: TreeNode) -> None:
    # remainder of function

Documentation

You should help future users of your function understand what your function does and how to use it properly, without needing to read the code, by providing a """docstring""" at the start of the function. A user may then type help(postOrderTraversal), which would print out that information.

You should help future maintainers of the code (including yourself) understand how the code works by including comments in the code, to describe the overall algorithm, and any non-obvious aspects. It is clear Charles Merriam did not understand the point of checking if popped == stack[-1].right, so that could definitely stand a comment or two.

Please note the distinction between “users of” and “maintainers of”. A user needs a docstring describing what the function does, what it needs and what it returns. A maintainer needs comments in the code describing how the code functions.

Iterative Algorithm

When you first visit a node, you push it on the stack, so you can return to it a second time, and then proceed to walk down the left branch.

When you return to the node, you leave it on the stack, so you can return to it a third time, and then you proceed to walk down the right branch.

When you again return to the node the third time, you finally “process” the node ... by popping it off the stack and printing its value.

You maintain a state machine using curr, popped and stack[-1].right to determine whether this is the first, second, or third visit to the node, which is somewhat complicated, despite you and your wife finding it “easy to grasp.”

Instead, consider pushing both the node and the state information onto the stack.

    stack.append((curr, False))
    curr = curr.left

And pop both pieces off the stack:

    curr, visited_right = stack.pop()
    if visited_right:
        print(curr.val)
        curr = None
    else:
        stack.append((curr, True))
        curr = curr.right

With this change, you no longer need to maintain and check popped against stack[-1].right. The state is stored along with the node on the stack.