Ternary tree preoder traversal (recursive implementation)

Question

Problem statement:

Print out to console the ternary tree preorder traversal. Suppose that the tree can have at most 3 children, left, middle and right. Preorder traversal is to visit the middle child first, and then left, and then right. Every node has integer value.

My introduction of Algorithm

I was asked to write a simple recursive algorithm two years ago at the end of an important meeting. I like the algorithm, so I reviewed the algorithm and wrote a short C# solution today.

I am planning to study a few of short C# courses by myself on pluralsight.com called "defensive code in C#", "Code Contracts", "Provable Code", learn to write better C# code in next 2 weeks. I am learning C# right now.

I am trying to get some critics on my practice today.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TernaryTreePreorderTraversal
{
    class TernaryTree
    {
        static void Main(string[] args)
        {
            RunTestcase(); 
        }

        /*
         * Ternary tree: 
         *      1
         *    / | \
         *   3  2  5
         *  /|  |
         * 4 33 22
         */
        public static void RunTestcase()
        {
            var root = new TernaryTree(1);

            root.Middle = new TernaryTree(2);
            root.Left   = new TernaryTree(3);
            root.Right  = new TernaryTree(4);

            root.Middle.Middle = new TernaryTree(22);
            root.Left.Middle   = new TernaryTree(33);
            root.Right = new TernaryTree(5);

            TernaryTree.PreOrderTraversal(root); 

            // manually verify the console output is 1 2 22 3 33 4 5
        }

        public TernaryTree Left   { get; set; }
        public TernaryTree Right  { get; set; }
        public TernaryTree Middle { get; set; }
        public int Data { get; set; }

        public TernaryTree(int val)
        {
            Data = val;
        }

        public static void PreOrderTraversal(TernaryTree node)
        {
            if (node == null)
            {
                return;
            }

            Console.WriteLine(node.Data);        

            PreOrderTraversal(node.Middle);     
            PreOrderTraversal(node.Left);       
            PreOrderTraversal(node.Right);     
        }
    }    
}

Answer 1

Class Definition

First of all, I would separate the class definition from the actual use case. The challenge wants you to walk nodes with integer data, but a next challenge may ask you to use a string instead. Don't let the use case stipulate the class definition. Let's make a generic class to make the tree reusable for more scenarios.

public class TernaryTree<T>
{
    public T Data { get; set; }
    public TernaryTree<T> Left { get; set; }
    public TernaryTree<T> Right { get; set; }
    public TernaryTree<T> Middle { get; set; }
}

DRY Code

You then present a method PreOrderTraversal which combines walking the tree with outputting data for this use case. It's a pitty the flow is not split from the use case. We would have to rewrite that flow for every single use case like this. Let's keep it DRY.

We want to have a non specific flow for traversing the tree pre-order, middle, left, then right.

public IEnumerable<TernaryTree<T>> WalkPreOrder()
{
    yield return this;
    foreach (var descendant in Middle?.WalkPreOrder())
    {
        yield return descendant;
    }
    foreach (var descendant in Left?.WalkPreOrder())
    {
        yield return descendant;
    }
    foreach (var descendant in Right?.WalkPreOrder())
    {
        yield return descendant;
    }
}

Use Case

And now we can reuse that method for our use case. This code should not be part of TernaryTree but rather of our unit test, or container class for the challenge:

 static void Print(TernaryTree<int> tree)
 {
     foreach (var node in tree.WalkPreOrder())
     {
         Console.WriteLine(node.Data);
     }
 }

Unit Tests

I noticed a comment in your code // manually verify the console output is 1 2 22 3 33 4 5. You can avoid manually checking the outcome by writing unit tests.

---

What's Next?

Since you can set any node to any of the child positions, you might introduce cycles. Suppose you set node.Left = node, this would be a cycle because of a self-to-child reference. As a challenge, you should try to figure out how to prevent cycles.

public TernaryTree Left   { get; set; }
public TernaryTree Right  { get; set; }
public TernaryTree Middle { get; set; }