Traversal.cs

// my solution to https://www.reddit.com/r/cscareerquestions/comments/450l6r/how_do_you_even_approach_a_really_tough_problem/
void Main()
{
	var tree = new Node("A",
		new Node("B",
			new Node("D"),
			new Node("E")),
		new Node("C",
			new Node("F"),
			new Node("G")));
			
	Traverse(tree).Select(n => n.Name).Dump();
}

public IEnumerable<Node> Traverse(Node root)
{
	var queue = new Queue<Node>();
	queue.Enqueue(root);
	
	while (queue.Count > 0)
	{
		var node1 = queue.Dequeue();
		
		var stack = new Stack<Node>();
		
		while (node1 != null)
		{
			stack.Push(node1);
			node1 = node1.Left;
		}
		
		while (stack.Count > 0)
		{
			var node2 = stack.Pop();
			
			yield return node2;
			
			if (node2.Right != null)
				queue.Enqueue(node2.Right);
		}
	}
}

public class Node
{
	public Node Left, Right;
	public string Name;
	
	public Node(string name, Node left = null, Node right = null)
	{
		Name = name;
		Left = left;
		Right = right;
	}
}