C# Binary Tree's - Inorder/Preorder and PostOrder (Recursion Help)

Question

I need some help with recursion. I'm trying do a binary tree in C#, I'm wondering if it's possible to demonstrate all Inorder/PostOrder and PreOrder traversal with a recursive function.

I have completed it for PreOrder and then attempted InOrder however caused a StackOverflow Exception, my grasp on Binary Tree's is flimsy at best so any help with this would be much appreciated, even if it does seem like a stupid question.

The following code is what I'm using for PreOrder Traversal;

     public void recursivePreorder(BinaryTreeNode root)
    {
        Console.Write(root.Data.ToString());
        if (root.Left != null)
        {
            recursivePreorder(root.Left);
        }
        if (root.Right != null)
        {
            recursivePreorder(root.Right);
            }
    }

     public void preorderTraversal()
    {
        if (Root != null)
        {
            recursivePreorder(Root);
        }
        else
        {
            Console.WriteLine("There is no tree to process");
        }

    static void Main(string[] args)
    {

        // Build the tree
        Test.Add(5);
        Test.Add(2);
        Test.Add(1);
        Test.Add(3);
        Test.Add(3); // Duplicates are OK
        Test.Add(4);
        Test.Add(6);
        Test.Add(10);
        Test.Add(7);
        Test.Add(8);
        Test.Add(9);
        // Test if we can find values in the tree

        for (int Lp = 1; Lp <= 10; Lp++)
            Console.WriteLine("Find Student ID ({0}) = {1}", Lp, Test.Find(Lp));

        // Test if we can find a non-existing value
        Console.WriteLine("Find Student ID (999) = {0}", Test.Find(999));

        // Iterate over all members in the tree -- values are returned in sorted order
        foreach (int value in Test)
        {
            Console.WriteLine("Value: {0}", value);
        }

        Console.WriteLine("Preorder Traversal");
        Console.WriteLine("");
        Test.preorderTraversal();
        Console.WriteLine("");
    }

Thanks in advance, this is definitely something I'm having trouble getting my head around and I'm not even sure if it's possible.

Answer 1

Inorder is very similar to what you already have, just move your code around a little bit in where you are handling the current node:

public void recursiveInorder(BinaryTreeNode root)
{
    if (root.Left != null)
    {
        recursiveInorder(root.Left);
    }
    Console.Write(root.Data.ToString());
    if (root.Right != null)
    {
        recursiveInorder(root.Right);
    }
}

The difference to preorder is just that you first traverse the left subtree, then process the current node and finally traverse the right subtree.

Answer 2

The wiki page for tree traversal states:

Binary Tree

To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node:

1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.

To traverse a non-empty binary tree in inorder (symmetric), perform the following operations recursively at each node:

1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.

[BTW, it was the first search hit.]