Tree Traversals

The Idea

Visiting every node means choosing when to handle the node itself. Preorder handles it before its children, inorder between the left and right subtrees, and postorder after both. One tree, one recursion, a single line moved.

Real-World Example

A conference programme. The announcer reads a track's title before any of its talks, which is preorder. The organiser totalling that track's runtime cannot write the number down until every talk inside it has been added up, and that is postorder.

The Code

class Node:
    def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r

root = Node("B", Node("A"), Node("C"))

def preorder(n):  return [] if not n else [n.val] + preorder(n.left) + preorder(n.right)
def inorder(n):   return [] if not n else inorder(n.left) + [n.val] + inorder(n.right)
def postorder(n): return [] if not n else postorder(n.left) + postorder(n.right) + [n.val]

print(preorder(root))   # ['B', 'A', 'C']  node first
print(inorder(root))    # ['A', 'B', 'C']  node in the middle
print(postorder(root))  # ['A', 'C', 'B']  node last

class Node:
  def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r

t = Node(2, Node(1), Node(3))

def walk(n):
  if not n: return []
  return walk(n.left) + ___ + walk(n.right)

print(walk(t))   # should print [1, 2, 3]