BinaryTree<T> written in C#

I've written a binary-tree using .NET Core 3.0. What can I do to improve my coding style?

using System;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;

namespace BinaryTree
{
/// <summary>
/// Represents a binary tree <seealso href="https://en.wikipedia.org/wiki/Binary_tree"/>.
/// </summary>
/// <typeparam name="T">The type which this tree should contain.</typeparam>
[Serializable]
[DataContract]
public class BinaryTree<T> where T : IComparable, new()
{
#if DEBUG
/// <summary>
/// Determines whether or not to log actions in the console.
/// </summary>
public static bool Log = true;
#endif

[DataMember]
private Node<T> _parentNode;

public BinaryTree()
{
#if DEBUG
if (Log)
Console.WriteLine("Initializing binary-tree..");
#endif
_parentNode = new Node<T>();
}

/// <summary>
/// Adds the specific item inside the binary-tree using binary-tree logic.
/// </summary>
/// <param name="item">The item that will be added.</param>
{
#if DEBUG
if (Log)
Console.WriteLine("Initializing binary-tree..");
#endif
}

/// <summary>
/// Removes the specific item inside the binary-tree using binary-tree logic. The root node cannot be removed.
/// </summary>
/// <param name="item">The item that will be removed.</param>
public void Remove(T item)
{
_parentNode.Remove(item);
}

/// <summary>
/// Searches for a specific item inside this binary-tree using binary-tree logic.
/// </summary>
/// <param name="item"></param>
/// <returns>Returns the count of said item if existing - 0 if otherwise.</returns>
public int Contains(T item)
{
return _parentNode.Contains(item);
}

/// <summary>
/// Clears everything out of this binary-tree.
/// </summary>
public void Clear()
{
_parentNode = new Node<T>();
}

public override bool Equals(object obj)
{
return obj is BinaryTree<T> tree && tree._parentNode.Equals(_parentNode);
}

public void Serialize(string file)
{
using (var writer = new StreamWriter(file))
{
var bf = new BinaryFormatter();
bf.Serialize(writer.BaseStream, this);
}
}

public static BinaryTree<T> Deserialize(string file)
{
{
var bf = new BinaryFormatter();
}
}

/// <summary>
/// Represents a node of a binary-tree. This may be either a simple node, a parent, or a leaf.
/// </summary>
/// <typeparam name="T">The type which this node should contain.</typeparam>
[Serializable]
[DataContract]
private class Node<T> where T : IComparable, new()
{
/// <summary>
/// Right "lower" arm of current node - this is where everything bigger than this node is getting redirect towards.
/// </summary>
[DataMember]
private Node<T> _bigger;

/// <summary>
/// Saved data and count of data - inside this specific node.
/// </summary>
[DataMember]
private (T data, int count) _item;

/// <summary>
/// Root node, if existing.
/// </summary>
[DataMember]
private Node<T> _parent;

/// <summary>
/// Left "lower" arm of current node - this is where everything smaller than this node is getting redirect towards.
/// </summary>
[DataMember]
private Node<T> _smaller;

private Node(T item)
{
_item = (item, 1);
}

public Node()
{
}

public override bool Equals(object obj)
{
return obj is Node<T> node &&
(node._bigger?.Equals(_bigger) ?? _bigger == null) &&
(node._item.data?.Equals(_item.data) ?? _item.data == null) &&
(node._item.count.Equals(_item.count)) &&
(node._parent?.Equals(_parent) ?? _parent==null) &&
(node._smaller?.Equals(_smaller) ?? _smaller == null);
}

private void Set(T data)
{
if (_item.data.Equals(default(T)))
{
_item = (data, 1);
return;
}

if (data.Equals(_item.data))
_item.count++;
else
}

public void Remove(T data)
{
if (data.Equals(_item.data))
{
if (_item.count > 1)
{
_item.count--;
}
else
{
if (_parent == null) return;

var replacement = new Node<T>(data)
{
_smaller = _smaller,
_bigger = _bigger,
_parent = _parent
};

if (_parent._item.data.CompareTo(_item.data) == 1)
_parent._smaller = replacement;
else
_parent._bigger = replacement;
}
}
else
{
if (data.CompareTo(_item.data) == 1)
{
_bigger?.Remove(data);
if (_bigger != null) _bigger._parent = this;
}
else
{
_smaller?.Remove(data);
if (_smaller != null) _smaller._parent = this;
}
}
}

{
if (_item.data.Equals(default(T)))
{
Set(item);
return;
}

if (item.CompareTo(_item.data) == 1)
{
#if DEBUG
if (Log)
Console.WriteLine($"{item} > {_item.data} → move to right lower node.."); #endif (_bigger = CreateOrReturnNode(_bigger)).Set(item); } else { #if DEBUG if (Log) Console.WriteLine($"{item} < {_item.data} → move to left lower node..");
#endif
(_smaller = CreateOrReturnNode(_smaller)).Set(item);
}
}

public int Contains(T value)
{
if (_item.data.Equals(value))
{
#if DEBUG
if (Log)
Console.WriteLine("Item was found!");
#endif
return _item.count;
}

if (value.CompareTo(_item.data).Equals(1))
{
#if DEBUG
if (Log)
Console.WriteLine($"{value} > {_item.data} → search in right lower node.."); #endif return _bigger?.Contains(value) ?? 0; } #if DEBUG if (Log) Console.WriteLine($"{value} < {_item.data} → search in left lower node..");
#endif
return _smaller?.Contains(value) ?? 0;
}

/// <summary>
/// Either creates a new node, or returns the existing one.
/// </summary>
/// <param name="node">The node which is getting checked whether it is set or not.</param>
/// <returns>Either a new node, or the already existing one.</returns>
private static Node<T> CreateOrReturnNode(Node<T> node = null)
{
return node ?? new Node<T>();
}
}
}
}


Updated Version: https://github.com/TheRealVira/binary-tree/blob/master/BinaryTree/BinaryTree.cs

• Is this finished? _parent doesn't seem to be touched outside Remove, so it looks like you were half-way through a refactor to either add or remove the field. – Peter Taylor Feb 12 '19 at 9:07
• @PeterTaylor I have added some comments and serialization options to it, but the _parent is as is "finished". It seemed like the easiest and quickest way to solve the removal process. – TheRealVira Feb 12 '19 at 9:10
• Please, please remove the #if DEBUG everywhere... consider having one method do your logging, marked with [ConditionalCompilation("DEBUG")], to achieve the same outcome without #if all over the place. – BittermanAndy Feb 12 '19 at 12:13
• I have updated my code to the newest version. – TheRealVira Feb 12 '19 at 12:53

    public class BinaryTree<T> where T : IComparable, new()


I suspect that you are unaware of the possibility of writing

    public class BinaryTree<T> where T : IComparable<T>, new()


If you did deliberately choose IComparable over IComparable<T>, it would be helpful to add a comment explaining why.

Why where T : new()? The code doesn't call new T() anywhere.

The class would be a lot more powerful if you also implemented IEnumerable<T>, and ideally you would implement ICollection<T>.

        private Node<T> _parentNode;


Node is an inner class, so it doesn't need the type parameter. You can remove it, and T from the outer class will be in scope. If you've come to C# from Java then note that this is one of the bigger differences in their type systems.

#if DEBUG
if (Log)
Console.WriteLine("Initializing binary-tree..");
#endif


If you use System.Diagnostics.Debug.WriteLine then (a) you can skip all the #if DEBUG; (b) when running in Visual Studio the log will be available in the Output pane even after the process has finished.

Alternatively you could take it up a level and use a proper runtime-configurable logging library like Serilog, log4net, ...

        public void Add(T item)
{
#if DEBUG
if (Log)
Console.WriteLine("Initializing binary-tree..");
#endif
}


That log message looks suspicious...

Also, I see you've made a design decision to push the majority of the logic into the nodes. Since you appear to be doing this as a learning exercise, I suggest that for comparison you separately implement a version which leaves the nodes as pure data objects and puts all the logic in the methods of BinaryTree. That lets you use tail optimisation (turn recursion into a while loop).

        public override bool Equals(object obj)
{
return obj is BinaryTree<T> tree && tree._parentNode.Equals(_parentNode);
}


Visual Studio gives me a warning about this: when you override Equals you should override GetHashcode because otherwise you will spend ages debugging if you ever put an instance of this class in a HashSet<> or as the key in a Dictionary.

The same applies to Node.

            /// <summary>
/// Right "lower" arm of current node - this is where everything bigger than this node is getting redirect towards.
/// </summary>
[DataMember]
private Node<T> _bigger;


I managed to understand the code ok, but it would be more conventional to call this _right. (Or maybe right, but I don't want to be pedantic about that kind of naming convention).

            private (T data, int count) _item;


That count is unusual. In effect you're implementing an IDictionary<T, int>: perhaps it would make sense to generalise to IDictionary<TKey, TValue> and have a separate wrapper class which turns any IDictionary<TKey, TValue> into a counter.

            public override bool Equals(object obj)
{
return obj is Node<T> node &&
(node._bigger?.Equals(_bigger) ?? _bigger == null) &&
(node._item.data?.Equals(_item.data) ?? _item.data == null) &&
(node._item.count.Equals(_item.count)) &&
(node._parent?.Equals(_parent) ?? _parent==null) &&
(node._smaller?.Equals(_smaller) ?? _smaller == null);
}


ValueStruct overrides ==, so you could simplify this a bit. Unless you want to be paranoid and assume that T might not have Equals consistent with CompareTo, in which case you should use CompareTo here to compare _item.data.

            public void Remove(T data)
{
if (data.Equals(_item.data))
{
if (_item.count > 1)
{
_item.count--;
}
else
{
if (_parent == null) return;


The only place that _parent is touched is in Remove, so if I add one item to the tree and then call Remove with that same item, it won't be removed.

            public int Contains(T value)
{
if (_item.data.Equals(value))


I got a NullReferenceException here when I called Contains on an empty tree.

            public void Add(T item)
{
if (_item.data.Equals(default(T)))


I got a NullReferenceException here when the tree was empty: did you test this code at all?

                        if (_parent._item.data.CompareTo(_item.data) == 1)
if (data.CompareTo(_item.data) == 1)
if (item.CompareTo(_item.data) == 1)
if (value.CompareTo(_item.data).Equals(1))


The contract of IComparable does not say that the value returned will always be -1, 0, or 1. I'm not sure why lots of people seem to think that it does. You should always compare the return value against 0.

• So, as far as I understood your reply, in this scenario it would be better to check if a value is greater then 0? Thank you for your reply! – TheRealVira Feb 12 '19 at 10:20
• Yes. The foolproof way of using CompareTo is to write the code without it: if (_data > _item.data), then move the RHS to the argument of CompareTo and replace it with 0: if (_data.CompareTo(_item.data) > 0). – Peter Taylor Feb 12 '19 at 10:26
• I need "where T : IComparable, new()" for my Clear function. This is where I have to create a new node. – TheRealVira Feb 12 '19 at 10:32
• You create a new Node<T>(), but not a new T(). – Peter Taylor Feb 12 '19 at 10:34
• I have updated my code and is now accessible on my github repo: github.com/TheRealVira/binary-tree/blob/master/BinaryTree/… – TheRealVira Feb 12 '19 at 13:06

Well, I would prefer not to have a private Node class inside the BinaryTree class. I think that the logic for adding/removing nodes in the tree should be done at the Tree class and not at the Node class level.

Maybe move the Node class into its own file, rename it to BinaryNodeTree and move the add/remove logic to the tree itself, which can use a utility class for searching the node to add the value too.

• This would probably also solve my _parent "problem". Thx! – TheRealVira Feb 12 '19 at 10:14
• Why pollute the namespace with a BinaryNodeTree class? The scope in which it will be used is inside the tree, so the class belongs inside the tree. – Peter Taylor Feb 12 '19 at 10:16
• @PeterTaylor this may be since my teacher, a "java specialist", tried to teach me to do that and called it good practice. – TheRealVira Feb 12 '19 at 10:22
• @PeterTaylor Also this is why I have wanted to learn by myself lol – TheRealVira Feb 12 '19 at 10:22
• @TheRealVira, in case it's not clear, I'm disagreeing with Shai Aharoni. Moving the logic out of the node is probably a good idea, and I also suggested that, but in my opinion moving the Node class outside the BinaryTree class offers only disadvantages. – Peter Taylor Feb 12 '19 at 10:33