4.3.2.1 - Tree traversals (C#)

Pre-order, in-order and post-order

A tree traversal visits every node in a defined order. For a binary tree, describe that order relative to the current node and its left and right subtrees; a subtree is itself processed using the same rule.

Use this exact binary tree, whose child relationships are also supplied in the table.

[DIAGRAM: asset_slug: traversal-tree; description: Binary tree with root M, left child F and right child T; F has children B and H; T has left child P and no right child.]

Pre-order starts with M, then visits the whole F subtree before T: M, F, B, H, T, P. In-order finishes F's left subtree B, outputs F, then H; it then outputs M and processes the T subtree: B, F, H, M, P, T. Post-order outputs B and H before their parent F; then P before T; M is last: B, H, F, P, T, M.

The words “pre”, “in” and “post” describe when the current node is visited. They do not mean moving across the page one row at a time. Level-order would be a different traversal.

Tracing recursive visits

Recursive traversal works because every call handles one subtree and returns to its caller when that subtree is finished. An empty child provides the base case, preventing a call from attempting to dereference no node.

Here is a complete static C# example of in-order traversal. Node? permits a missing child; the null check occurs before any field is read.

using System;
class Node
{
    public string Value;
    public Node? Left;
    public Node? Right;
    public Node(string value) { Value = value; }
}
class Program
{
    static void InOrder(Node? node)
    {
        if (node == null) return;
        InOrder(node.Left);
        Console.WriteLine(node.Value);
        InOrder(node.Right);
    }
    static void Main()
    {
        Node root = new Node("M");
        root.Left = new Node("F");
        root.Right = new Node("T");
        root.Left.Left = new Node("B");
        root.Left.Right = new Node("H");
        root.Right.Left = new Node("P");
        InOrder(root);
    }
}

For the first output, the active calls are M → F → B. B calls its empty left child, which immediately returns; B then outputs itself. After B's empty right call, control returns to F, where the statement after InOrder(node.Left) outputs F. Each call retains its own node reference. Returning from B does not replace F's reference with B.

Move the output before both calls for pre-order, or after both calls for post-order. Keep the left-before-right order. On a leaf, each version outputs that leaf once. On an empty tree, each produces no output.