Preorder and Postorder Traversal
Chapter Sixty
Syllabus topic Module 2, "Trees: Implementation and Traversals"
Pages 183 to 185 of 411
In one line
Preorder visits the node before its subtrees and postorder after them, and the choice is not arbitrary: preorder copies a tree, postorder destroys one, and inorder reads one.
The one line that differs
preorder (node): visit(node); go left; go right
inorder (node): go left; visit(node); go right
postorder(node): go left; go right; visit(node)
Three identical functions with one statement moved. Everything else about them is the same.
All three, run on one tree
class BNode:
__slots__ = ("data", "left", "right")
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
# F
# / .
# B G
# / . .
# A D I
# / . /
# C E H
tree = BNode("F",
BNode("B", BNode("A"), BNode("D", BNode("C"), BNode("E"))),
BNode("G", None, BNode("I", BNode("H"), None)))
def preorder(node, out=None):
out = [] if out is None else out
if node is not None:
out.append(node.data)
preorder(node.left, out)
preorder(node.right, out)
return out
def inorder(node, out=None):
out = [] if out is None else out
if node is not None:
inorder(node.left, out)
out.append(node.data)
inorder(node.right, out)
return out
def postorder(node, out=None):
out = [] if out is None else out
if node is not None:
postorder(node.left, out)
postorder(node.right, out)
out.append(node.data)
return out
print("preorder :", " ".join(preorder(tree)))
print("inorder :", " ".join(inorder(tree)))
print("postorder:", " ".join(postorder(tree)))
print()
print("the root F is: first in preorder, in the middle in inorder, last in postorder")
print(" preorder[0] =", preorder(tree)[0])
print(" postorder[-1] =", postorder(tree)[-1])
print(" inorder position of F =", inorder(tree).index("F"), "of", len(inorder(tree)))preorder : F B A D C E G I H
inorder : A B C D E F G H I
postorder: A C E D B H I G F
the root F is: first in preorder, in the middle in inorder, last in postorder
preorder[0] = F
postorder[-1] = F
inorder position of F = 5 of 9Two facts to carry from that run, and both are used in chapter 63:
The root is first in preorder and last in postorder. Always. That is how a tree is rebuilt from its traversals.
Inorder gives the sorted order, as chapter 59 proved.
What each traversal is actually for
This is the part that makes the three worth separating.
Preorder copies a tree
To copy a tree you must create a node before you can attach its children, so you need the node first: that is preorder.
The same reason makes preorder the order in which a tree is written out to a file and read back: the parent must exist before its children can be attached to it.
Postorder destroys a tree, and computes from the bottom up
To free a node you must free its children first, or you lose the addresses of the subtrees. So deletion of a whole tree is postorder, and in C this is not optional.
Preorder and Postorder Traversal
More generally, postorder is for anything where a node's answer depends on its children's answers: the height of a node, the size of a subtree, the value of an expression. The children must be finished before the parent can be computed.
Inorder reads a search tree
Chapter 59.
class BNode:
__slots__ = ("data", "left", "right")
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
# an expression tree for (3 + 5) x 2
expression = BNode("x", BNode("+", BNode("3"), BNode("5")), BNode("2"))
def preorder(node, out=None):
out = [] if out is None else out
if node is not None:
out.append(node.data)
preorder(node.left, out)
preorder(node.right, out)
return out
def inorder_bracketed(node):
if node is None:
return ""
if node.left is None and node.right is None:
return node.data
return "(%s %s %s)" % (inorder_bracketed(node.left), node.data,
inorder_bracketed(node.right))
def postorder(node, out=None):
out = [] if out is None else out
if node is not None:
postorder(node.left, out)
postorder(node.right, out)
out.append(node.data)
return out
def evaluate(node):
"""Postorder in spirit: the children must be computed before the node."""
if node.left is None and node.right is None:
return int(node.data)
left, right = evaluate(node.left), evaluate(node.right)
return left + right if node.data == "+" else left * right
def copy_tree(node):
"""Preorder in spirit: the node must exist before its children attach."""
if node is None:
return None
new = BNode(node.data)
new.left = copy_tree(node.left)
new.right = copy_tree(node.right)
return new
def freed_order(node, out=None):
"""Postorder: a node's children are freed before the node itself."""
out = [] if out is None else out
if node is not None:
freed_order(node.left, out)
freed_order(node.right, out)
out.append(node.data)
return out
print("an expression tree for (3 + 5) x 2")
print(" preorder gives PREFIX :", " ".join(preorder(expression)))
print(" inorder gives INFIX :", inorder_bracketed(expression))
print(" postorder gives POSTFIX:", " ".join(postorder(expression)))
print()
print("evaluating it needs the children first, which is postorder:",
evaluate(expression))
print()
copy = copy_tree(expression)
print("copying needs the node first, which is preorder.")
print(" the copy evaluates to the same:", evaluate(copy))
print(" and it is a different object :", copy is not expression)
print()
print("freeing a tree must free children before parents:")
print(" order freed:", " ".join(freed_order(expression)))an expression tree for (3 + 5) x 2
preorder gives PREFIX : x + 3 5 2
inorder gives INFIX : ((3 + 5) x 2)
postorder gives POSTFIX: 3 5 + 2 x
evaluating it needs the children first, which is postorder: 16
copying needs the node first, which is preorder.
the copy evaluates to the same: 16
and it is a different object : True
freeing a tree must free children before parents:
order freed: 3 5 + 2 xPreorder and Postorder Traversal
The three traversals of an expression tree are exactly the three notations of chapter 36. That is not a coincidence: prefix, infix and postfix are preorder, inorder and postorder of the expression's tree, and saying so is a good answer to "what connects stacks and trees".
The costs
All three are O(n) time and O(h) space for the recursion stack, as chapter 59 said. They differ only in the order of the output, not in cost.
Quick revision
- The three recursive traversals differ by one statement: where
visit(node)sits. - Preorder: node, left, right. Inorder: left, node, right. Postorder: left, right, node.
- The root is first in preorder and last in postorder, always.
- Preorder copies a tree and writes it to a file: the node must exist before its children attach.
- Postorder frees a tree and computes anything that depends on the children: height, size, the value of
an expression.
- Inorder reads a search tree in order.
- On an expression tree the three traversals give prefix, infix and postfix exactly.
- All three are O(n) time and O(h) space.
Test yourself
1. Write all three traversals, showing the one line that moves. Each visits the node and recurses left then right; preorder visits before the two calls, inorder between them, postorder after them.
2. Where is the root in each traversal's output? First in preorder, last in postorder, and between the left and right subtrees' values in inorder.
3. Why must copying a tree use preorder? Because the node has to be created before its children can be attached to it.
4. Why must freeing a tree use postorder, and why is this not optional in C? Because freeing a node first would lose the addresses of its subtrees, which are stored in it, leaving the children unreachable and leaked.
5. Give the three traversals of an expression tree for (3 + 5) x 2. Preorder x + 3 5 2 which is prefix; inorder ((3 + 5) x 2) which is infix; postorder 3 5 + 2 x which is postfix.
6. Which traversal computes a node's height, and why that one? Postorder, because a node's height depends on its children's heights, so the children must be finished before the node can be computed.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.