Traversal of Binary Tree (Simplest Example)

Implementation of Inorder, Preorder, and Postorder traversal or a binary tree / binary search tree. Learn to implement binary tree traversal methods: Inorder, Preorder, and Postorder. Code examples are provided for traversing nodes in specific orders in both binary trees and binary search trees.

To create a Binary search tree, follow my previous post: Basic Binary search tree (BST) implementation. We can implement the following programs in a simple binary tree or Binary search tree. 

In this post, we will write three simple methods to implement binary tree traversal. Let's start with some theory. 

Traversing a binary tree refers to visiting and processing each node in the tree in a specific order. There are three common methods for traversing binary trees:

1. Inorder Traversal: In an inorder traversal, the nodes are visited in the order: left subtree, current node, right subtree. This traversal method is commonly used for binary search trees to visit the nodes in sorted order.
2. Preorder Traversal: In a preorder traversal, the nodes are visited in the order: current node, left subtree, right subtree.
3. Postorder Traversal: In a postorder traversal, the nodes are visited in the order left subtree, right subtree, and current node.

We will take the following tree for reference.

Coding implementation

public class Node
{
    public int Data { get; set; }
    public Node? Left { get; set; }
    public Node? Right { get; set; }
    public Node(int val)
    {
        Data = val; 
    }
}

public class BinarySearchTree
{
    private readonly Node _root;
    public BinarySearchTree(int value)
    {
        _root = new Node(value);
    }

    public Node Root
    {
        get { return _root; }
    }

    public void PrintInOrder(Node node)
    {
        if (node == null)
            return;
        Console.Write($"|{node.Data}|  ");
        PrintInOrder(node.Left);
        PrintInOrder(node.Right);
    }

    public void PrintPreOrder(Node node)
    {
        if (node == null)
            return;
        PrintPreOrder(node.Left);
        Console.Write($"|{node.Data}|  ");
        PrintPreOrder(node.Right);
    }

    public void PrintPostOrder(Node node)
    {
        if (node == null)
            return;
        PrintPostOrder(node.Left);
        PrintPostOrder(node.Right);
        Console.Write($"|{node.Data}|  ");
    }


    public void Insert(int value)
    {
        Node currentNode = _root;
        Node parent = _root;

        while (currentNode != null)
        {
            parent = currentNode;
            if (value < currentNode.Data)
            {
                currentNode = currentNode.Left;
            }
            else
            {
                currentNode = currentNode.Right;
            }
        }

        if (value < parent.Data)
        {
            parent.Left = new Node(value);
        }
        else
        {
            parent.Right = new Node(value);
        }
    }
    
}

 

Printing Output :

BinarySearchTree binarySearchTree = new BinarySearchTree(12);
binarySearchTree.Insert(3);
binarySearchTree.Insert(442);
binarySearchTree.Insert(2);
binarySearchTree.Insert(78);
binarySearchTree.Insert(-90);
binarySearchTree.Insert(55);
binarySearchTree.Insert(90);

Console.WriteLine($"\nInOrder : ");
binarySearchTree.PrintInOrder(binarySearchTree.Root);

Console.WriteLine("\nPre-Order : ");
binarySearchTree.PrintPreOrder(binarySearchTree.Root);

Console.WriteLine("\nPost-Order : ");
binarySearchTree.PrintPostOrder(binarySearchTree.Root);

  

Note. Make sure to add null check in recusrive method, or else the program will break when the null node will come into picture.  

Inorder Traversal

public void PrintInOrder(Node node)
{
    if (node == null)
        return;

    Console.Write($"|{node.Data}|  ");
    PrintInOrder(node.Left);
    PrintInOrder(node.Right);
}

 Preorder Traversal

public void PrintPreOrder(Node node)
{
    if (node == null)
        return;

    PrintPreOrder(node.Left);
    Console.Write($"|{node.Data}|  ");
    PrintPreOrder(node.Right);
}

Postorder Traversal

public void PrintPostOrder(Node node)
{
    if (node == null)
        return;

    PrintPostOrder(node.Left);
    PrintPostOrder(node.Right);
    Console.Write($"|{node.Data}|  ");
}