MARCIN.com

A node in a binary tree can contain zero, one, or two child nodes. You can traverse a binary tree in three common approaches, namely pre-order, in-order, and post-order, as you will see below. However, first let's implement a tree, starting with the class representing a binary tree:

public class BinaryTree<T>
{
    public BinaryTreeNode<T>? Root { get; set; } 
    public int Count { get; set; } 
}

A single node is represented by the following class:

public class BinaryTreeNode<T>
{
    public T? Data { get; set; }
    public BinaryTreeNode<T>? Parent { get; set; }
    public BinaryTreeNode<T>? Left { get; set; } = null!;
    public BinaryTreeNode<T>? Right { get; set; } = null!;
}

Coming back to the traversal methods, let's start with the pre-order approach. Here, you first visit the root node. Then, you visit the left child. Finally, the right child is visited. Of course, such a rule does not apply only to the root node, but to any node in a tree. For this reason, you can understand the order of pre-order traversal as first visiting the current node, then its left child (the whole left subtree using the pre-order approach recursively), and finally its right child (the right subtree in a similar way). The code, as a method in the BinaryTree class, is presented below:

private void TraversePreOrder(BinaryTreeNode<T> node, List<BinaryTreeNode<T>> result)
{
    if (node == null) { return; }
    result.Add(node);
    TraversePreOrder(node.Left, result);
    TraversePreOrder(node.Right, result);
} 

The second traversal mode is called in-order. It differs from the pre-order approach in the order that nodes are visited in: first the left child, then the current node, and then the right child:

private void TraverseInOrder(BinaryTreeNode<T> node, List<BinaryTreeNode<T>> result)
{
    if (node == null) { return; }
    TraverseInOrder(node.Left, result);
    result.Add(node);
    TraverseInOrder(node.Right, result);
}

The last traversal mode is named post-order and supports the following order of node traversal: the left child, the right child, then the current node, as shown below:

private void TraversePostOrder(BinaryTreeNode<T> node, List<BinaryTreeNode<T>> result)
{
    if (node == null) { return; }
    TraversePostOrder(node.Left, result);
    TraversePostOrder(node.Right, result);
    result.Add(node);
}

The main Traverse method is presented as follows:

public List<BinaryTreeNode<T>> Traverse(string mode)
{
    List<BinaryTreeNode<T>> nodes = [];
    if (Root == null) { return nodes; }
    switch (mode)
    {
        case "pre": TraversePreOrder(Root, nodes); break;
        case "in": TraverseInOrder(Root, nodes); break;
        case "post": TraversePostOrder(Root, nodes); break;
    }
    return nodes;
}

This entry can contain content, including parts of code, from one of my books, namely from the Second Edition of C# Data Structures and Algorithms, published by Packt Publishing in 2024. If you want to get detailed description of trees, including binary trees and binary search trees, as well as about many other data structures, I encourage you to take a look at the mentioned book. You can buy it here.

The content, including any part of code, is presented without warranty, either express or implied. The author cannot be held liable for any damages caused or alleged to have been caused directly or indirectly by any content shown on this website.