Tree traversal using recursion in C#

Tree traversal refers to the process of visiting and accessing all nodes in a tree data structure in a specific order. Recursive tree traversal involves using recursion to traverse the tree, visiting each node and its children in a particular sequence. The three common types of recursive tree traversal are in-order, pre-order, and post-order traversal.

1. In-order Tree Traversal:
In in-order traversal, the left subtree is visited first, then the current node, and finally the right subtree. For binary search trees (BST), the nodes are visited in ascending order.


public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val)
    {
        this.val = val;
        this.left = this.right = null;
    }
}

public class TreeTraversal
{
    public void InOrderTraversal(TreeNode root)
    {
        if (root == null)
            return;

        InOrderTraversal(root.left);
        Console.Write(root.val + " ");
        InOrderTraversal(root.right);
    }
}

2. Pre-order Tree Traversal:
In pre-order traversal, the current node is visited first, followed by the left subtree, and then the right subtree.


public class TreeTraversal
{
    public void PreOrderTraversal(TreeNode root)
    {
        if (root == null)
            return;

        Console.Write(root.val + " ");
        PreOrderTraversal(root.left);
        PreOrderTraversal(root.right);
    }
}

3. Post-order Tree Traversal:
In post-order traversal, the left subtree is visited first, then the right subtree, and finally the current node.


public class TreeTraversal
{
    public void PostOrderTraversal(TreeNode root)
    {
        if (root == null)
            return;

        PostOrderTraversal(root.left);
        PostOrderTraversal(root.right);
        Console.Write(root.val + " ");
    }
}

Binary Tree Traversal Using Recursion:
Binary trees are a specific type of tree where each node has at most two children: left and right. The recursive tree traversal methods mentioned above can be applied to binary trees as well.

Here's an example of using the recursive methods for binary tree traversal:


public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val)
    {
        this.val = val;
        this.left = this.right = null;
    }
}

public class BinaryTraversal
{
    public void InOrderTraversal(TreeNode root)
    {
        if (root == null)
            return;

        InOrderTraversal(root.left);
        Console.Write(root.val + " ");
        InOrderTraversal(root.right);
    }

    public void PreOrderTraversal(TreeNode root)
    {
        if (root == null)
            return;

        Console.Write(root.val + " ");
        PreOrderTraversal(root.left);
        PreOrderTraversal(root.right);
    }

    public void PostOrderTraversal(TreeNode root)
    {
        if (root == null)
            return;

        PostOrderTraversal(root.left);
        PostOrderTraversal(root.right);
        Console.Write(root.val + " ");
    }
}

public class Program
{
    public static void Main()
    {
        // Create a sample binary tree:
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        BinaryTraversal traversal = new BinaryTraversal();

        Console.WriteLine("In-order Traversal:");
        traversal.InOrderTraversal(root);
        Console.WriteLine();

        Console.WriteLine("Pre-order Traversal:");
        traversal.PreOrderTraversal(root);
        Console.WriteLine();

        Console.WriteLine("Post-order Traversal:");
        traversal.PostOrderTraversal(root);
        Console.WriteLine();
    }
}

When you run this program, you'll see the output for in-order, pre-order, and post-order traversals of the binary tree. The output will be as follows:


In-order Traversal:
4 2 5 1 6 3 7

Pre-order Traversal:
1 2 4 5 3 6 7

Post-order Traversal:
4 5 2 6 7 3 1

C# - Tree Traversal Using Recursion

Subscribe to Newsletter