Get next node in PreOrder Traversal without calling from a loop

[Divya Prakash Jha]

I know it's straight forward to write the code for a pre order traversal of the Binary tree. My requirement is that I want to get Next node from any random node from the pre order traversed list. Note Next node should be fetched on demand basis and not necessarily from a foreach loop at caller side. Preferably this Next method needs to be an extension method and should be called on a given Node.

I am thinking to use some sort of "yield" to maintain a state, but my restriction is that extension method's signature I can not modify. It should strictly return Node object and NOT IEnumerable.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{
class Program
{
static void Main(string[] args)
{
var r = new Node(1,
new Node(2, null, null),
new Node(3, null, null));

// I know I can do a preorder and get Next node one by one in a loop
var list = new List<Node>();
PreOrder(r, list);
foreach (var item in list)
{
Console.WriteLine(item.data);
}

// But I want to call it in following way. Note I can call Next on any random node of the tree.
var next = r.Next();
Console.WriteLine(next.data);

next = next.Next();
Console.WriteLine(next.data);

next = next.Next();
Console.WriteLine(next.data);
}
static void PreOrder(Node node, List<Node> list)
{
if (node == null) return;
list.Add(node);
PreOrder(node.left, list);
PreOrder(node.right, list);
}
}
public class Node
{
public Node left;
public Node right;
public int data;

public Node(int d, Node l, Node r)
{
data = d;
left = l;
right = r;
}
}
public static class NodeExtensions
{
public static Node Next(this Node node)
{
// I want to implement this
}
}
}

Continue reading...