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)
{
result.Add(currentNode);
}
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) { result.Add(currentNode); } for (int i = 0; i < result.Count; i++) { Assert.AreEqual(i+1, result[i]); } } } public class DemoTreeIterator<T> : IEnumerator<T> { private readonly DemoTree<T> _tree; 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; } } }
