Дано упорядоченное дерево глубины N (N > 0 — четное)

private static void Main()
{
    var paths = new List<Path>();
    SetPaths(paths, 4, new Path(), 0);
 
    foreach (Path path in paths)
    {
        Console.WriteLine($"Path {path} with weight {path.Weight}");
    }
}
 
private static void SetPaths(ICollection<Path> paths, int n, Path path, int level)
{
    level++;
    if (level == n)
    {
        if (path.Length > 0)
        {
            paths.Add(path);
        }
    }
    else if (level < n)
    {
        SetPaths(paths, n, Path.Add(path, NodeType.Left, 1), level);
        SetPaths(paths, n, Path.Add(path, NodeType.Right, -1), level);
    }
}
 
public class Path
{
    public List<NodeType> Nodes { get; set; } = new List<NodeType>();
    public int Weight { get; set; }
    public int Length => Nodes.Count;
 
    public static Path Add(Path path, NodeType type, int weight)
    {
        return new Path
        {
            Nodes = new List<NodeType>(path.Nodes) { type },
            Weight = path.Weight + weight
        };
    }
 
    public override string ToString()
    {
        return string.Join(", ", Nodes);
    }
}
 
public enum NodeType
{
    Left,
    Right
}