#nullable enable

​

using System;

​

var values = new[] { 50, 25, 75, 10, 30, 5, 7, 3, 70, 80 };

​

Node<int>? returnTree = null;

foreach(var value in values)

    returnTree = TreeInsert(returnTree, value);

​

Console.WriteLine("Tree built using return values");

DumpTree(returnTree);

​

Node<int>? refTree = null;

foreach (var value in values)

    TreeInsertRef(ref refTree, value);

​

Console.WriteLine("Tree built using ref parameters");

DumpTree(refTree);

​

​

Node<T> TreeInsert<T>(Node<T>? node, T value) where T : IComparable<T>

{

    if (node == null)

        return new Node<T>(value);

​

    var compare = value.CompareTo(node.Value);

    if (compare < 0)

        node.Left = TreeInsert<T>(node.Left, value);

    else if (compare > 0)

        node.Right = TreeInsert<T>(node.Right, value);

    else

        throw new InvalidOperationException();

    return node;

}

​

void TreeInsertRef<T>(ref Node<T>? node, T value) where T : IComparable<T>

{

    if (node == null)

    {

        node = new Node<T>(value);

        return;

    }

​

    var compare = value.CompareTo(node.Value);

    if (compare < 0)

    {

        var temp = node.Left;

        TreeInsertRef<T>(ref temp, value);

        node.Left = temp;

    }

    else if (compare > 0)

    {

        var temp = node.Right;

        TreeInsertRef<T>(ref temp, value);

        node.Right = temp;

    }

    else

    {

        throw new InvalidOperationException();

    }

}

​

void DumpTree<T>(Node<T>? root)

{

    if (root == null)

        return;

​

    Console.WriteLine(root.Value);

    DumpChild("", root.Left, root.Right != null);

    DumpChild("", root.Right, false);

​

    void DumpChild(string pad, Node<T>? node, bool hasSibling)

    {

        if (node == null)

            return;

​

        Console.Write(pad);

        Console.Write(hasSibling ? "+-" : "--");

        Console.WriteLine(node.Value);

​

        pad += hasSibling ? "| " : "  ";

        DumpChild(pad, node.Left, node.Right != null);

        DumpChild(pad, node.Right, false);

    }

}

​

class Node<T>

{

    public T Value { get; set; }

    public Node<T>? Left { get; set; }

    public Node<T>? Right { get; set; }

​

    public Node(T value) => Value = value;

}

​