Binary Tree Traversal Methods

Binary trees (BTs) are data structures used by computer programmers whose software must represent medium to large data sets in an organized, structured manner. A BT consists of a parent node with a maximum of two optional child nodes: a left child and a right child. Application-specific data structures such as search trees, heaps and expression trees are simply collections of individual BTs linked together to form a collective data set. There are three distinct methods for traversing BTs: preorder traversal, inorder traversal and postorder traversal.

Preorder Traversal

Preorder traversal visits tree nodes in this sequence: parent, left child, right child. Some applications of preorder traversal are the evaluation of expressions in prefix notation and the processing of abstract syntax trees by compilers. The following pseudocode demonstrates the exact procedure for a preorder traversal:

----------------------
PROCEDURE PreOrder (Binary_Tree_Node T)
BEGIN
ProcessNode(T)
If (T's left child is NOT NULL)
BEGIN
PreOrder(T's left child)
END
If (T's right child is NOT NULL)
BEGIN
PreOrder(T's right child)
END
END

Inorder Traversal

Inorder traversal visits tree nodes in this sequence: left child, parent, right child. Binary search trees (a special type of BT) use inorder traversal to print all of their data in alphanumeric order. The following pseudocode demonstrates the exact procedure for an inorder traversal:

----------------------
PROCEDURE InOrder (Binary_Tree_Node T)
BEGIN
If (T's left child is NOT NULL)
BEGIN
InOrder(T's left child)
END
ProcessNode(T)
If (T's right child is NOT NULL)
BEGIN
InOrder(T's right child)
END
END
---------------------

Postorder Traversal

Postorder traversal visits tree nodes in this sequence: left child, right child, parent. A popular application for the use of postorder traversal is the evaluating of expressions in postfix notation. The following pseudocode demonstrates the exact procedure for a postorder traversal:

----------------------
PROCEDURE PostOrder (Binary_Tree_Node T)
BEGIN
If (T's left child is NOT NULL)
BEGIN
PostOrder(T's left child)
END
If (T's right child is NOT NULL)
BEGIN
PostOrder(T's right child)
END
ProcessNode(T)
END
---------------------

Resources

• Stanford CS Ed Library: Binary Trees by Nick Parlante