4
\$\begingroup\$

This is a simple implementation of a generic binary tree that holds elements of type T. I was wondering if there was something that could be done better (especially in the EnumerateNodes methods).

using System.Collections.Generic;

namespace DataStructures.Node
{
    /// <summary>
    /// Implements a generic binary tree.
    /// </summary>
    /// <typeparam name="T">The type of the nodes</typeparam>
    public class Node<T>
    {
        #region Private attributes
        private T _node = default(T);
        private Node<T> _leftChild = default(Node<T>);
        private Node<T> _rightChild = default(Node<T>);
        #endregion

        #region Constructor
        public Node()
        {
            _node = default(T);
            _leftChild = null;
            _rightChild = null;
        }

        public Node(T node)
        {
            _node = node;
            _leftChild = null;
            _rightChild = null;
        }
        #endregion

        #region Accessors
        public T Value
        {
            get { return _node; }
            set { _node = value; }
        }

        public Node<T> LeftChild
        {
            get { return _leftChild; }
            set { _leftChild = value; }
        }

        public Node<T> RightChild
        {
            get { return _rightChild; }
            set { _rightChild = value; }
        }

        /// <summary>
        /// Returns the total number of elements in the tree.
        /// </summary>
        public int Count
        {
            get { return count(); }
        }
        #endregion

        #region Private methods

        private int count()
        {
            if (_leftChild == null && _rightChild == null)
                return 1;
            if (_leftChild == null)
                return 1 + _rightChild.count();
            if (_rightChild == null)
                return 1 + _leftChild.count();
            else
                return 1 + _leftChild.count() + _rightChild.count();
        }

        #endregion

        #region Public methods

        /// <summary>
        /// Adds the element on the right branch of the node.
        /// </summary>
        /// <param name="rightBranch">Node to add on the right side of the node.</param>
        public void AddRight(Node<T> rightBranch)
        {
            _rightChild = rightBranch;
        }

        /// <summary>
        /// Adds the element on the left branch of the node.
        /// </summary>
        /// <param name="leftBranch">Node to add on the left side of the node.</param>
        public void AddLeft(Node<T> leftBranch)
        {
            _leftChild = leftBranch;
        }

        public IEnumerable<T> EnumerateNodes()
        {
            yield return _node;
            if (_leftChild != null)
                foreach (T child in _leftChild.EnumerateNodes())
                    yield return child;
            if (_rightChild != null)
                foreach (T child in _rightChild.EnumerateNodes())
                    yield return child;
        }

        #endregion
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ If you can guarantee that your binary-tree will always be balanced then you can optimize storage by storing elements in an array T[] (orList<T>) - which helps avoid heap fragmentation. \$\endgroup\$
    – Dai
    Jun 21, 2016 at 0:48

2 Answers 2

5
\$\begingroup\$

Auto Properties

If you're not really doing anything in your properties, other than passing values back and forth to a backing field, you should consider using auto properties instead.

    public T Value
    {
        get { return _node; }
        set { _node = value; }
    }

Becomes:

    public T Value {get;set;}

And the backing fields get removed, internal code then accesses the value via the property.

Duplication

I'm not really keen on your Left + Right nodes being as exposed as they are, it's possible for clients of your class to build their own trees, which might be what you want, but it feels odd, what happens if they do myNode.LeftChild = myNode? That said, your LeftNode property and AddLeft method do the same thing, they both overwrite the current LeftNode with a new one. I assumed AddLeft was going to recursively call until it found an empty left node and then add it. If they are intended to do the same thing, then I'd think about removing one of them.

Too much control outside of the class

Consider this loop, which never ends:

int count = 0;
Node<int> head = new Node<int>();
head.AddRight(head);

foreach(var node in head.EnumerateNodes())
{
    Console.WriteLine($"{count++}");
}

default(Node<T>) Vs null

I don't really have a strong preference, but if you're initialising to default(Node<T>) then you should probably test for it in your enumerator, or initialise to null. Whichever one you choose, be consistent.

\$\endgroup\$
5
\$\begingroup\$

Here's an alternative way to write count(). It's shorter and uses expressions instead of statements. You can't do as much in an expression, so I use them instead of statements when possible because there's a lower chance of things going wrong. Readability is more important than those things, though, so I recommend using what is most readable to you.

private int count()
{
    return 1 +
        (_leftChild != null ? _leftChild.count() : 0) +
        (_rightChild != null ? _rightChild.count() : 0);
}

Or if you want to use C# 6 null checking:

private int count()
{
    return 1 + (_leftChild?.count() ?? 0) + (_rightChild?.count() ?? 0);
}

Method names should be UpperCamelCase, so count() should be Count(). I'm guessing you want to access a child's Count property instead of the method because the method is private.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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