using System;

using System.Collections.Generic;

using System.Linq;

using Newtonsoft.Json;

​

public class Program

{

    public static void Main()

    {

        var list = new List<int> { 4, 2, 1, 3, 5, 6 };

        Node root = null;

        for (var i = 0; i < list.Count; ++i)

        {

            root = Tree.insert(root, list[i]);

        }

        Tree.traverse(root);

        var res = BTSSequences(root);

        Console.WriteLine(JsonConvert.SerializeObject(res));

    }

    static List<List<int>> BTSSequences(Node root)

    {

        List<Node> roots = new List<Node> { root };

        return BTSSequences(roots);

    }

    static List<List<int>> BTSSequences(List<Node> roots)

    {

        var output = new List<List<int>>();

        for (var i = 0; i < roots.Count; i++)

        {

            var choices = roots.ToList(); // make a copy

            var root = choices[i];

            choices.RemoveAt(i);

            choices.AddRange(new[] { root.Left, root.Right }.Where(c => c != null).ToList());

            if (choices.Count > 0)

            {

                var itemsList = BTSSequences(choices);

                foreach (var items in itemsList)

                {

                    output.Add(new[] { root.Value }.Concat(items).ToList());

                }

            }

            else

            {

                output.Add(new[] { root.Value }.ToList());

            }

        }

        return output;

    }

}

​

class Node

{

    public int Value;

    public Node Left;

    public Node Right;

}

​

class Tree

{

    public static Node insert(Node root, int val)

    {

        if (root == null)

        {

            root = new Node();

            root.Value = val;

        }

        else if (val < root.Value)

        {

            root.Left = insert(root.Left, val);

        }

        else

        {

            root.Right = insert(root.Right, val);

        }

        return root;

    }

    public static void traverse(Node root)

    {

        if (root == null) return;

        Console.WriteLine(root.Value);

        traverse(root.Left);

        traverse(root.Right);

    }

}

​