Tree Traversal

Refers to the process of [see page 16, enumerating] the nodes of a binary tree.

Pre-order Tree Traversal

Is a tree traversal algorithm which yields the current element before branching into the left and right sub-trees.

def pre_order(x):
    if x is not None:
	print(x.key)
	pre_order(x.left)
	pre_order(x.right)

Code Snippet 1: Pre-order tree traversal.

Is a tree traversal algorithm which branches into the left sub-tree, yields the current element and then branches into the right sub-tree.

def in_order(x):
    if x is not None:
	in_order(x.left)
	print(x.key)
	in_order(x.right)

Code Snippet 2: In-order tree traversal.

Is a tree traversal algorithm which branches into both sub-trees before yielding the current element.

def post_order(x):
    if x is not None:
	post_order(x.left)
	post_order(x.right)
	print(x.key)

Code Snippet 3: Post-order tree traversal.