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&lt;int&gt; res = ConvertTreeToList(root);

        }

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

        private List&lt;int&gt; ConvertTreeToList(TreeNode root)
        {
            List&lt;int&gt; res = new List&lt;int&gt;();
            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&lt;int&gt; 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&lt;int&gt; 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&lt;int&gt; ConvertTreeToList(TreeNode root)
{
    var result = new List&lt;int&gt;();
    ConvertTreeToList(root, result);
    return result;
}