Binary Search Tree Bypass - PreOrder

Question

I am trying to implement a Tree Traversal PreOrder using a return return that returns IEnumerable

private IEnumerable<T> Preorder(Node<T> node) { while(node != null) { yield return node.Data; yield return node.LeftChild.Data; yield return node.RightChild.Data; } } 

In this case, it goes into an infinite loop, and yes, I know that I need to continue moving. How can I do that?

If LeftChild or RightChild is NULL, throws a null exception. I think at this moment I need a break output;

I assume that both the order and the order after recording will be similar, any ideas?

I have a recursive version that works well.

 public void PreOrderTraversal(Node<T> node) { if(node!=null) { Console.Write(node.Data); } if (node.LeftChild != null) { PreOrderTraversal(node.LeftChild); } if (node.RightChild != null) { PreOrderTraversal(node.RightChild); } } 

Thanks.

Answer 1

Option number 1 Recursive

 public class Node<T> : IEnumerable<T> { public Node<T> LeftChild { get; set; } public Node<T> RightChild { get; set; } public T Data { get; set; } public IEnumerator<T> GetEnumerator() { yield return Data; if (LeftChild != null) { foreach (var child in LeftChild) yield return child; } if (RightChild != null) { foreach (var child in RightChild) yield return child; } } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); } } 

Using:

 var child1 = new Node<int> { Data = 1 }; var child2 = new Node<int> { Data = 2 }; var child3 = new Node<int> { Data = 3, LeftChild = child1 }; var root = new Node<int> { Data = 4, LeftChild = child3, RightChild = child2 }; foreach (var value in root) Console.WriteLine(value); 

Option number 2 non-recursive static method

 public static IEnumerable<T> Preorder<T>(Node<T> root) { var stack = new Stack<Node<T>>(); stack.Push(root); while (stack.Count > 0) { var node = stack.Pop(); yield return node.Data; if (node.RightChild != null) stack.Push(node.RightChild); if (node.LeftChild != null) stack.Push(node.LeftChild); } }