# Iterator for BFS binary tree traversal

I implemented an iterator pattern for C# using IEnumerator and IEnumerable. The goal of the implementation is to traverse a binary tree.

using System.Collections;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace DesignPatternsQuestions
{
[TestClass]
public class TreeNodeTest
{
[TestMethod]
public void IteratorTreeNodeTest()
{
TreeNode<int> treeNodeList = new TreeNode<int>();
TreeNode<int> left = new TreeNode<int> { Value = 2 };
TreeNode<int> leftLeft = new TreeNode<int> { Value = 4 };
TreeNode<int> leftRight = new TreeNode<int> { Value = 5 };
left.Left = leftLeft;
left.Right = leftRight;
TreeNode<int> right = new TreeNode<int> { Value = 3 };
TreeNode<int> rightLeft = new TreeNode<int> { Value = 6 };
TreeNode<int> rightRight = new TreeNode<int> { Value = 7 };
right.Right = rightRight;
right.Left = rightLeft;
treeNodeList.Value = 1;
treeNodeList.Right = right;
treeNodeList.Left = left;

List<int> result = new List<int>();
foreach (var currentNode in treeNodeList)
{
}

for (int i = 0; i < result.Count; i++)
{
Assert.AreEqual(i+1, result[i]);
}
}
}
public class TreeNode<T> : IEnumerable<T>
{
public TreeNode<T> Left { get; set; }
public TreeNode<T> Right { get; set; }

public T Value { get; set; }
public IEnumerator<T> GetEnumerator()
{
return new TreeNodeIterator<T>(this);
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}

public class TreeNodeIterator<T> : IEnumerator<T>
{
private TreeNode<T> _tree;
private TreeNode<T> _current;
private Queue<TreeNode<T>> Q = new Queue<TreeNode<T>>();
public TreeNodeIterator(TreeNode<T> treeNode)
{
_tree = treeNode;
if (_tree != null)
{
Q.Enqueue(_tree);
}

}

public bool MoveNext()
{
if (_tree == null)
{
Reset();
return true;
}
else
{

while (Q.Count > 0)
{
_current = Q.Dequeue();
if (_current.Left != null)
{
Q.Enqueue(_current.Left);
}
if (_current.Right != null)
{
Q.Enqueue(_current.Right);
}
return true;
}
}
return false;
}

public void Reset()
{
_current = null;
}

public void Dispose()
{

}

object IEnumerator.Current
{
get { return Current; }
}

public T Current
{
get { return _current.Value; }
}
}
}


Just for comparison, here is code from a PluralSight design pattern course that I used as a model for my solution, but with children() function and different type of Queue nodes. Don't review the pluralsight code.

They are very close however I wanted to know what would you prefer, thinking about code simplicity and also pretending that this is a 30-minute interview question?

What I like about the Plural sight code is that it calls children function which is good also not only for binary tree. What I do not like about his code is the fact that you store a Queue of IEnumerator<DemoTree<T>>. I think that in a real coding interview you can do a lot of mistakes with this approach.

Please also comment on style or anything else you find critical for job interviews.

using System;
using System.Collections;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace DesignPatternsQuestions
{
//implement the iterator interface and use it for traversing a binary tree
//this is how the plural sight guy did it
[TestClass]
public class IteratorPatternTest
{
[TestMethod]
public void PrintBinaryTreeTest()
{
DemoTree<int> treeNodeList = new DemoTree<int>();
DemoTree<int> left = new DemoTree<int> { Value = 2 };
DemoTree<int> leftLeft = new DemoTree<int> { Value = 4 };
DemoTree<int> leftRight = new DemoTree<int> { Value = 5 };
left.Left = leftLeft;
left.Right = leftRight;
DemoTree<int> right = new DemoTree<int> { Value = 3 };
DemoTree<int> rightLeft = new DemoTree<int> { Value = 6 };
DemoTree<int> rightRight = new DemoTree<int> { Value = 7 };
right.Right = rightRight;
right.Left = rightLeft;
treeNodeList.Value = 1;
treeNodeList.Right = right;
treeNodeList.Left = left;

List<int> result = new List<int>();
foreach (var currentNode in treeNodeList)
{
}

for (int i = 0; i < result.Count; i++)
{
Assert.AreEqual(i+1, result[i]);
}
}
}

public class DemoTreeIterator<T> : IEnumerator<T>
{
private DemoTree<T> _current;

public Queue<IEnumerator<DemoTree<T>>> Q = new Queue<IEnumerator<DemoTree<T>>>();

//must have a ctor to passing tree to the Iterator
public DemoTreeIterator(DemoTree<T> tree)
{
_tree = tree;
}
public bool MoveNext()
{
if (_current == null)
{
Reset();
_current = _tree;
Q.Enqueue(_current.Childern().GetEnumerator());
return true;
}
while (Q.Count > 0)
{
var enumerator = Q.Peek();
if (enumerator.MoveNext())
{
_current = enumerator.Current;
Q.Enqueue(_current.Childern().GetEnumerator());
return true;
}
else
{
Q.Dequeue();
}
}

return false;
}

public void Reset()
{
_current = null;
}

public void Dispose()
{
}

public T Current
{
get { return _current.Value; }
}
object IEnumerator.Current
{
get { return Current; }
}
}

public class DemoTree<T> : IEnumerable<T>
{
public T Value { get; set; }
public DemoTree<T> Left { get; set; }
public DemoTree<T> Right { get; set; }

public IEnumerator<T> GetEnumerator()
{
return new DemoTreeIterator<T>(this);
}
//backward compatible without Generic
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}

//a way to return all the children
public IEnumerable<DemoTree<T>> Childern()
{
if (Left != null)
{
yield return Left;
}
if (Right != null)
{
yield return Right;
}
yield break;
}
}
}

• You named the two versions in the wrong order... and we cannot review the code from Pluralsight... you have quote it. I don't think this would be even possible as a comparative-review. You can however use it as a reference thus the quote. – t3chb0t Aug 12 '18 at 8:13
• @t3chb0t thanks always for answering so quickly. I didn't mean that you review the Pluralsight code of course. I just wanted to ask you as an interviewer which one would you prefer and why? I don't like the usage of some of it code and I do like some of it. So i thought you can review my code and tell your opinion as well. Thanks – Gilad Aug 12 '18 at 8:20
• I'd be great if you could summarize your solution and explain it in more details. Tell us what you like about it, what you don't like, why you solved things in a certain way. How you are going to use it and why. What problem it solves etc. I must admit I have absolutely no idea what your question is about :-( – t3chb0t Aug 12 '18 at 8:46
• @t3chb0t ok I changed it, should I just remove the PluralSight code? is it too confusing? – Gilad Aug 12 '18 at 8:53
• You can leave it there as a reference (however formatted as a quote). Then you could write something like I used this code as an inspriation and changed the following things because... and here comes your solution and its description - I did this because I think it's good, I dropped that because I think it's a bad idea and instead I did this... I think if you presented it like that then it would make an interesting question. – t3chb0t Aug 12 '18 at 8:59

I'll ignore the 'PluralSight' code.

Note that you have implemented a breadth-first traversal. As far as I'm concerned, a spec which doesn't specify how the tree is traversed is insufficient, but you must document this behaviour (e.g. with inline documentation (///), or otherwise make a statement that the order is undefined (otherwise people will unwittingly assume it is dependable). Assumptions should always be documented in some manner (ideally via the type system, otherwise through exceptions, and finally as inline documentation and comments)

## Constructor

TreeNodeIterator will fail if you pass null to the constructor, with MoveNext always returning true, and Current throwing a confusing NullReferenceException. Throw in the constructor! In your recent questions, you've done a lot of checking for null, but not nearly enough of throwing ArgumentExceptions. Fail fast with good error messages, and your API will be significantly harder to misuse.

Of course, if you want to support accepting a null Tree (which would be an empty tree) then this will need change elsewhere in the code, and would warrant documentation.

## MoveNext() and Reset()

What is this doing?

if (_tree == null)
{
Reset();
return true;
}


This says "if I was supplied null, then please perpetually pretend I have data... or otherwise never run me".

My guess is that this was meant to check _current, and that Reset() is meant to clear the queue, and requeue _tree (which it should do, as part of the IEnumerator contract). This has not been achieved, which makes the Enumerator single-use (without documentation to support this). You also shouldn't be calling Reset from MoveNext(): IEnumerators shouldn't auto-reset (though I can't find an authoritative reference for this...).

Also, that while should be an if. I'd be inclined to make it an else if, which would reduce the nesting, and make the 3 possible paths much clearer. Stripping the _tree == null gives you a much cleaner method:

public bool MoveNext()
{
if (Q.Count > 0)
{
_current = Q.Dequeue();

if (_current.Left != null)
{
Q.Enqueue(_current.Left);
}

if (_current.Right != null)
{
Q.Enqueue(_current.Right);
}

return true;
}
else
{
return false;
}
}


## TreeNode<T>

I'm guessing you were proscribed the highly mutable TreeNode<T>. It's probably worth documenting that the iterator makes no attempt to handle the case where the data in a TreeNode<T> is changed during iteration, and that doing so is unsupported (unless you specifically try to support it in some way). It's also perfectly possible that nice TreeNode<T> to be part of a graph with cycles, in which case your iterator will never terminate (again, this might warrant documentation).

I'd also consider making the iterator internal or even private (within TreeNode<T>), since it is an implementation detail (judging by the lack of tests which don't go through TreenNode<T>, and the behaviour when passed null.

## Misc

• _tree and Q should probably be readonly.

• Q is a terrible and inconsistent name (i.e. private but upper-case with no underscore). _queue would be significantly better in the context. (You could argue that _queue is still not great, because it describes the thing, not what it does, which is to provide a traversal frontier, but I think it would be fine).

• You might consider throwing if Current is called before MoveNext. Some of the BCL throws InvalidOperationException, because it makes no sense to ask for a value which doesn't exist yet. However, other pats of it do not for (as far as I can gather) performance reasons. You also don't do anything to mitigate calling Current after MoveNext has returned false (e.g. it will continue to return whatever happened to be last rather than throw): again, the BCL is inconsistent in this regard between IEnumerator<T> and IEnumerator (more reasons to avoid manually enumerating things... (as opposed to using foreach)).

## Personal Preference Stuff

• A little more care given to white-space would be nice. You have a few seemingly randomly empty lines, and I'd personally want more padding in other places (e.g. between the back-to-back ifs, otherwise they can feel like an if, else if pair, and after the fields before the constructor)

• Empty methods (Dispose()) scare me. I always leave a comment in an empty method indicating that it is meant to be empty, otherwise it looks like I've forgotten to implement it. Doing nothing is kind-of-OK, but ideally this would set some internal state to indicate the IEnumerator has been disposed and can no-longer be used.

### Bug

There's a bug in your Reset method.

public void Reset()
{
_current = null;
}


It should also be resetting the Q and not only the _current field. With the current Reset you can call MoveNext and continue where you left. The very first call to MoveNext should execute Q.Enqueue(_tree); and not the constructor. This is, when _current is null.

Altenatively you can throw an exception:

The Reset method is provided for COM interoperability and does not need to be fully implemented; instead, the implementer can throw a NotSupportedException.

IEnumerator Interface

Personally I don't like this convention because it means you have to reinstantiate the enumerator. It's much better to actually implement the Reset correctly... if posssible.

• Why do you suggest not appending to the queue until the first call to MoveNext()? I'd have thought it would be simpler to have the constructor simply call Reset(), so that MoveNext() can be solely concerned with consuming the Queue; I am missing something? – VisualMelon Aug 12 '18 at 19:18
• @VisualMelon because until you call MoveNext the enumerator is in the out-of-range state and technically MoveNext moves or starts the enumerator not the constructor. MSDN says: Initially, the enumerator is positioned before the first element in the collection. You must call the MoveNext method to advance the enumerator to the first element of the collection before reading the value of Current; otherwise, Current is undefined. Another option is to throw an exception on Reset. – t3chb0t Aug 12 '18 at 19:26
• Right, but (at least in the OP's implementation) _current is populated from the queue in MoveNext: until the element is poped when MoveNext is first called, _current remains unset. – VisualMelon Aug 12 '18 at 19:31
• @VisualMelon anyways, Reset is not working as expected thus it's a bug and if you want to fix it, you have to move the code from the constructor to MoveNext ;-) – t3chb0t Aug 12 '18 at 19:33