11
\$\begingroup\$

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>
        public void Add(T item)
        {
#if DEBUG
            if (Log)
                Console.WriteLine("Initializing binary-tree..");
#endif
            _parentNode.Add(item);
        }

        /// <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)
        {
            using (var reader = new StreamReader(file))
            {
                var bf = new BinaryFormatter();
                return (BinaryTree<T>)bf.Deserialize(reader.BaseStream);
            }
        }

        /// <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
                    Add(data);
            }

            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;
                    }
                }
            }

            public void Add(T item)
            {
                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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Feb 12 at 9:07
  • \$\begingroup\$ @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. \$\endgroup\$ – TheRealVira Feb 12 at 9:10
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – BittermanAndy Feb 12 at 12:13
  • \$\begingroup\$ I have updated my code to the newest version. \$\endgroup\$ – TheRealVira Feb 12 at 12:53
23
\$\begingroup\$
    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
            _parentNode.Add(item);
        }

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.

\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – TheRealVira Feb 12 at 10:20
  • 2
    \$\begingroup\$ 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). \$\endgroup\$ – Peter Taylor Feb 12 at 10:26
  • \$\begingroup\$ I need "where T : IComparable, new()" for my Clear function. This is where I have to create a new node. \$\endgroup\$ – TheRealVira Feb 12 at 10:32
  • 2
    \$\begingroup\$ You create a new Node<T>(), but not a new T(). \$\endgroup\$ – Peter Taylor Feb 12 at 10:34
  • \$\begingroup\$ I have updated my code and is now accessible on my github repo: github.com/TheRealVira/binary-tree/blob/master/BinaryTree/… \$\endgroup\$ – TheRealVira Feb 12 at 13:06
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ This would probably also solve my _parent "problem". Thx! \$\endgroup\$ – TheRealVira Feb 12 at 10:14
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Feb 12 at 10:16
  • \$\begingroup\$ @PeterTaylor this may be since my teacher, a "java specialist", tried to teach me to do that and called it good practice. \$\endgroup\$ – TheRealVira Feb 12 at 10:22
  • \$\begingroup\$ @PeterTaylor Also this is why I have wanted to learn by myself lol \$\endgroup\$ – TheRealVira Feb 12 at 10:22
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor Feb 12 at 10:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.