6
\$\begingroup\$

The interview question was to traverse a tree into a list.

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

namespace ConsoleApplication2
{
    public class TreeToList
    {
        public TreeToList()
        {

            //            0 
            //        2         4
            //     6    8          10
            TreeNode root = new TreeNode(0);
            root.Left = new TreeNode(2);
            root.Right = new TreeNode(4);
            root.Left.Left = new TreeNode(6);
            root.Left.Right = new TreeNode(8);
            root.Right.Right = new TreeNode(10);

            List<int> res = ConvertTreeToList(root);

        }

        //pre-order 0 2 4
        //in-order 2 0 4
        //post-order 2 4 0

        private List<int> ConvertTreeToList(TreeNode root)
        {
            List<int> res = new List<int>();
            if (root != null)
            {
                res.Add(root.Index);
            }
            else
            {
                return null;
            }
            if(root.Left != null)
            {
                res.AddRange(ConvertTreeToList(root.Left));
            }
            if(root.Right != null)
            {
                res.AddRange(ConvertTreeToList(root.Right));
            }
            return res;
        }
    }
}

My output is:

0,2, 6, 8, 4, 10
\$\endgroup\$
11
\$\begingroup\$

You're creating a new List<int> for every node in the tree, which is a lot of garbage for the garbage collector. Each value will also end up getting appended to many temporary lists.

Let's kick the can down the road and assume that the work of creating the list has been taken care of for us. We take the result list as a parameter and append to that

private static void ConvertTreeToList(TreeNode root, List<int> result)
{
    if (root == null)
    {
        return;
    }

    result.Add(root.Index);
    ConvertTreeToList(root.Left, result);
    ConvertTreeToList(root.Right, result);
}

Now we just add a helper function

private static List<int> ConvertTreeToList(TreeNode root)
{
    var result = new List<int>();
    ConvertTreeToList(root, result);
    return result;
}
\$\endgroup\$
2
\$\begingroup\$

I don't understand the structure of your class. In the constructor, you create a tree, convert it to list, … and then do nothing with the result? Even ignoring that, this doesn't fit into what a constructor should do.

Also ConvertTreeToList() can be static, so it should be.


TreeNode root = new TreeNode(0);
root.Left = new TreeNode(2);
root.Right = new TreeNode(4);
root.Left.Left = new TreeNode(6);
root.Left.Right = new TreeNode(8);
root.Right.Right = new TreeNode(10);

You can use object initializers here:

TreeNode root = new TreeNode(0)
{
    Left = new TreeNode(2)
    {
        Left = new TreeNode(6),
        Right = new TreeNode(8)
    },
    Right = new TreeNode(4)
    {
        Right = new TreeNode(10)
    }
};

This makes the structure of the tree you're creating more visible in the code and it also repeats itself less.


return null;

Empty list should be represented by an empty list, not by null. This would simplify your code, since you wouldn't have to check for nulls before invoking the method recursively.


Using LINQ and IEnumerables instead of Lists, you could write your method like this:

private static IEnumerable<int> ConvertTreeToList(TreeNode root)
{
    if (root == null)
        return Enumerable.Empty<int>();

    return new[] { root.Index }
        .Concat(ConvertTreeToList(root.Left))
        .Concat(ConvertTreeToList(root.Right));
}

Efficiency-wise this is likely going to be better than your approach, because it doesn't copy lists for every node. Thought it's still not great, because an item from the bottom of the tree is going to be processed on every level.

So, if efficiency is important, I would prefer mjolka's solution. If not, I like my version better, because it's simpler and shorter.

(If you want to be more precise, both your original algorithm and my version are \$\mathcal{O}(n \cdot \log n)\$, while mjolka's is \$\mathcal{O}(n)\$.)

\$\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.