3
\$\begingroup\$

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);     
        }
    }    
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ when will the root be visited? \$\endgroup\$ – Vogel612 Feb 25 '17 at 21:14
  • \$\begingroup\$ @Vogel612, may I ask you to explain the question in more detail? I debugged the test case and it works as I showed in the C# comment. \$\endgroup\$ – Jianmin Chen Feb 25 '17 at 21:17
  • 1
    \$\begingroup\$ Usually traversing orderings also include when the root of a subtree is visited. Your traversal orders only include the children. When is the root of a subtree visited? \$\endgroup\$ – Vogel612 Feb 25 '17 at 21:19
  • \$\begingroup\$ @Vogel612, I guess that you like to ensure that the root node is visited first, and then children of ternary tree are visited. Here the statement of output: Console.WriteLine(node.Data); is the answer, visit the root means sending node's value to console. \$\endgroup\$ – Jianmin Chen Feb 25 '17 at 21:22
3
\$\begingroup\$

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; }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.