# My C# submission, easy-to-understand, >97% runtime distribution

• Basically this algorithm uses a Stack in combination with an alternating directional flag to recursively traverse the binary tree in a zig-zag pattern.

This is my first submission to a discussion so let me know if I can improve anything! Code can probably be cleaned up but the runtime is pretty efficient so I'll just post what I have.

Here's the code:

``````public class Solution
{
public IList<IList<int>> ZigzagLevelOrder(TreeNode root)
{
IList<IList<int>> order = new List<IList<int>>();

if (root == null)
{
return order;
}

Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
traverse(order, stack, false);

return order;
}

private void traverse(IList<IList<int>> order, Stack<TreeNode> stack, bool flag)
{
IList<int> currentRow = new List<int>();
Stack<TreeNode> nextRow = new Stack<TreeNode>();
flag = (flag) ? false : true; // flip traversal direction

while (stack.Count > 0)
{
TreeNode currentNode = stack.Pop();
if (flag) // traverse right --> left (add to stack in reverse)
{
if (currentNode.left != null)
{
nextRow.Push(currentNode.left);
}
if (currentNode.right != null)
{
nextRow.Push(currentNode.right);
}
}
else // traverse left --> right (add to stack in reverse)
{
if (currentNode.right != null)
{
nextRow.Push(currentNode.right);
}
if (currentNode.left != null)
{
nextRow.Push(currentNode.left);
}
}
}