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

Question

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

For this 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**

Joel Coehoorn · Accepted Answer · 2022-07-13 17:21:19Z

The issue here 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 handling nested/recursive conversions, 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

Update:

I thought about it some more, and with these four total implicit conversion definitions we can also allow the original data expression to work:

(TreeNode<T>, T, TreeNode<T>)
(T, T, TreeNode<T>)
(TreeNode<T>, T, T)
(T, T, T)

And the class:

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 static implicit operator TreeNode<T>((T, T, TreeNode<T>) t) => new TreeNode<T>(t.Item2) {Left = new TreeNode<T>(t.Item1),  Right=t.Item3};
    public static implicit operator TreeNode<T>((TreeNode<T>, T, T) t) => new TreeNode<T>(t.Item2) {Left = t.Item1,  Right=new TreeNode<T>(t.Item3)};
    public static implicit operator TreeNode<T>((T, T, T) t) => new TreeNode<T>(t.Item2) {Left = new TreeNode<T>(t.Item1),  Right=new TreeNode<T>(t.Item3)};
}


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

See it work with the original expressions:

https://dotnetfiddle.net/mGN7Lf
https://dotnetfiddle.net/6I32WU

Now we can even (sort of) write the original method. The actual type for the argument is still TreeNode<T>, but we can pass the tuple in and get the TreeNode out:

public static TreeNode TupleToBST<T>(TreeNode<T> tup)   //Line 36
{
    return tup;
}
TreeNode<int> tree = TupleToBST<int>( ( ( 1, 3, null), 2, ( ( null, 3, 4 ), 5, ( 6, 7, 8 ) ) ));

https://dotnetfiddle.net/ni7jJf

Note the method doesn't really do anything... it was the implicit conversions and the compiler that did all the work here.

YungDeiza · Accepted Answer · 2022-06-24 21:20:50Z

1

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

answered Jun 24, 2022 at 21:20

YungDeiza

4,8442 gold badges18 silver badges44 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

Update:

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Update:

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related