C# - Passing tuple of tuples as an input argument to a method-CodePudding

I am writing a method to create binary search tree using tuples. I have TreeNode class that creates a tree node.

class TreeNode
{
    public int Key{get; set;}
    public TreeNode Left{get; set;}
    public TreeNode Right{get; set;}

    public TreeNode(int key)
    {
        this.Key = key;
    }
}

I want to create the following tree Example BST and for that I am using the tuple value

( ( 1, 3, null), 2, ( ( null, 3, 4 ), 5, ( 6, 7, 8 ) ) ) which represents the BST in tuple form.

The method TupleToBST that creates BST using tuples, needs to take tuple of tuples as an input argument so that I could create BST recursively.

public static TreeNode TupleToBST(Tuple<Tuple, int, Tuple> tup)   //Line 36
  {
    if (tup == null)
    {
        return null;
    }
    TreeNode t = new TreeNode(tup.Item2);
    t.Left = TupleToBST(tup.Item1);
    t.right = TupleToBST(tup.Item3);
    return t;
  }

The main.cs file code is as follow:

static void Main ()
{
  var tup = Tuple.Create(Tuple.Create(1,3,null),2,Tuple.Create(Tuple.Create(null,3,4),5,Tuple.Create(6,7,8)));
  TreeNode tree = TupleToBST(tup);
  Console.WriteLine(tree.Right.Right.Key);
  Console.WriteLine(tree.Right.Right.Key);
}

I am getting the following error:

main.cs(36): error CS0718: `System.Tuple': static classes cannot be used as generic arguments**

CodePudding user response：

You can't really do what you are trying to do with a tuple because it would involve a recursive definition; your definition is not complete. You need to specify the type of each property in the tuple e.g. Tuple<Tuple<int,int>, int>. Without limiting the tree depth, you cannot do what you want to do.

I suggest another data structure. Using a linked list would be a simple way to implement this. Or you could create something like a recursive Tuple like in this previous question: Recursive tuple

CodePudding user response：

You will not be able to do this. The reason is you need types for the inner Tuples. So instead of this:

Tuple<Tuple, int, Tuple>

It has to look more like this:

Tuple<Tuple<Tuple, int Tuple>, int, Tuple<Tuple, int, Tuple>>

But now we've just pushed the problem down another level. We could in turn define those type arguments, but I think you get the idea that this problem never ends, and in fact grows exponentially with each new level.

Even worse, you can't just define a massive type with an arbitrarily sufficient number of levels to hold any practical tree. Instead, you'd have to define the type argument to exactly match the existing branches in your tree, or also define an overload for every possible size and balance level combination.

Therefore instead of Tuples you should use TreeNode:

class TreeNode<T>
{
    public T Key{get; set;}
    public TreeNode<T> Left{get; set;}
    public TreeNode<T> Right{get; set;}

    public TreeNode(T key)
    {
        this.Key = key;
    }
}

public static TreeNode<T> TupleToBST<T>((TreeNode<T>, T, TreeNode<T>) tup)
{
    if (tup == null) return null;

    // Tuple items start counting at 1, not 0
    return new TreeNode(tup.Item2) {Left = tup.Item1, Right = tup.Item3};
}

But I understand this is unlikely to satisfy you, because it seems like the goal is entering a single large expression into the code to create your data.

One option to consider is defining an implicit conversion from Tuple<TreeNode<T>, T, TreeNode<T>> to TreeNode<T>. I wasn't sure at first how the compiler would react to such a literal, but it's an idea worth exploring.

But before we can go down this path we need to talk about the data. Even if this does work, the question has this example data:

( ( 1, 3, null), 2, ( ( null, 3, 4 ), 5, ( 6, 7, 8 ) ) )

This data would be invalid, because only the center item is allowed to have values. The left and right sides must always be either null or another Tuples/TreeNode, and every leaf node must always look like (null, value null). You would instead need to show it like this:

( ( (null, 1, null), 3, null), 2, ( ( null, 3, (null, 4, null) ), 5, ( (null, 6, null), 7, (null, 8, null) ) ) )

Now that we have valid data, we can try our conversion. And — amazingly — this seems to work:

public class TreeNode<T>
{
    public T Key{get; set;}
    public TreeNode<T> Left{get; set;}
    public TreeNode<T> Right{get; set;}

    public TreeNode(T key)
    {
        this.Key = key;
    }
    public static implicit operator TreeNode<T>((TreeNode<T>, T, TreeNode<T>) t) => new TreeNode<T>(t.Item2) {Left = t.Item1,  Right=t.Item3};
}

public class Program
{
    public static void Main()
    {
        TreeNode<int> tree = ( ( (null, 1, null), 3, null), 2, ( ( null, 3, (null, 4, null) ), 5, ( (null, 6, null), 7, (null, 8, null) ) ) );
        Console.WriteLine(tree.Left.Key);
    }
}

You can see it yourself here:

https://dotnetfiddle.net/7XaHa4
https://dotnetfiddle.net/ZvUPYM