Tree traversal into List

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 res = ConvertTreeToList(root);

        }

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

        private List ConvertTreeToList(TreeNode root)
        {
            List res = new List();
            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

You're creating a new List 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 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 ConvertTreeToList(TreeNode root)
{
    var result = new List();
    ConvertTreeToList(root, result);
    return result;
}

StackExchange Code Review Q#73638, answer score: 11