Binary Search Tree Traversal - PreOrder

Question

I m trying to implement Tree Traversal PreOrder using yield return which returns an 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 infinite loop and yes I know that I need to keep traversing. How can this be done?

If the LeftChild or RightChild is null, throws a null exception. I think at that point i need yield break;

I assume, inorder and postorder would be similar too, any ideas?

I have the Resursive 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.

Alex Aza · Accepted Answer · 2011-06-04T04:06:04.387

Option #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();
    }
}

Usage:

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

see: http://stackoverflow.com/questions/1043050/c-performance-of-nested-yield-in-a-tree — Mitch Wheat, Jun 04 '11 at 03:08
That'll stop at the children without traversing any further. — user7116, Jun 04 '11 at 03:31
@user177883 - Your original question didn't mention that recursive option is not acceptable. I updated the answer with non-recursive approach. — Alex Aza, Jun 04 '11 at 04:01
+1, @Alex: you're right sir, my apologies. I did not copy/paste yours exactly (I'm going to stop coding at midnight now). — user7116, Jun 04 '11 at 04:02
One note, if using a stack you should push the right child before the left child to ensure preorder traversal. — user7116, Jun 04 '11 at 04:05

Binary Search Tree Traversal - PreOrder

1 Answers1