Tree Traversal

Tree traversal algorithms visit every node in a tree exactly once. There are three main traversal orders: pre-order, in-order, and post-order. All three are recursive (or can use a stack).

Pre-Order Traversal (Root → Left → Right)

Visit the root first, then recursively traverse the left subtree, then the right subtree.

PROCEDURE preOrder(node)
  IF node ≠ null THEN
    process(node)        // Visit root first
    preOrder(node.left)  // Then left subtree
    preOrder(node.right) // Then right subtree
  END IF
END PROCEDURE

Use: Copying or serialising a tree structure; prefix notation for expressions.

In-Order Traversal (Left → Root → Right)

Recursively traverse the left subtree, visit the root, then recursively traverse the right subtree.

PROCEDURE inOrder(node)
  IF node ≠ null THEN
    inOrder(node.left)   // Left subtree first
    process(node)        // Visit root in middle
    inOrder(node.right)  // Then right subtree
  END IF
END PROCEDURE

Key property: In-order traversal of a Binary Search Tree (BST) produces nodes in ascending sorted order.

Post-Order Traversal (Left → Right → Root)

Recursively traverse the left subtree, then the right subtree, then visit the root last.

PROCEDURE postOrder(node)
  IF node ≠ null THEN
    postOrder(node.left)  // Left subtree
    postOrder(node.right) // Right subtree
    process(node)         // Visit root last
  END IF
END PROCEDURE

Use: Deleting a tree (children must be deleted before parent); evaluating expression trees.

Worked Example

// Binary tree:
//         5
//        / \
//       3   8
//      / \   \
//     1   4   9

Pre-order:  5, 3, 1, 4, 8, 9   (Root first)
In-order:   1, 3, 4, 5, 8, 9   (Sorted — it's a BST)
Post-order: 1, 4, 3, 9, 8, 5   (Root last)

Expression Trees

An expression tree stores an arithmetic expression. Operators are internal nodes; operands are leaves.

// Expression: (3 + 4) × 2
//        ×
//       / \
//      +   2
//     / \
//    3   4

Pre-order  (prefix):  × + 3 4 2    → Polish notation
In-order   (infix):   3 + 4 × 2    → Infix (normal)
Post-order (postfix): 3 4 + 2 ×    → Reverse Polish Notation (RPN)

Comparison Summary