# ZigZag tree travesal

The question is taken for a coding interview I had, it is also in geeks for geeks, https://www.geeksforgeeks.org/zigzag-tree-traversal/

you are given a binary tree and you need to print it in a ZigZag/Snake order for level one from left to right and the next level from right to left and so on.

I was asked only to come up with a solution I used a queue and a stack in the real interview, when I coded it now I tried using 2 stacks.

Please review the code as if it was a real interview, complexity, coding style, assume I have 20-30 minutes to code. you can ignore the test case.

Thanks.

using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
[TestClass]
public class PrintBinaryTreeZigZag
{

[TestMethod]
public void PrintBinaryTreeZigZagTest()
{
BinaryTree root = new BinaryTree
{
Value = 1,
Left = new BinaryTree { Value = 2 },
Right = new BinaryTree { Value = 3 }
};
root.Left.Left = new BinaryTree { Value = 7 };
root.Left.Right = new BinaryTree { Value = 6 };
root.Right.Left = new BinaryTree { Value = 5 };
root.Right.Right = new BinaryTree { Value = 4 };
List<int> res = PrintBinaryZigZag(root);
List<int> expected = new List<int> { 1, 3, 2, 7, 6, 5, 4 };
CollectionAssert.AreEqual(expected, res);

}

public List<int> PrintBinaryZigZag(BinaryTree root)
{
if (root == null)
{
return null;
}
Stack<BinaryTree> currentLevel = new Stack<BinaryTree>();
Stack<BinaryTree> nextLevel = new Stack<BinaryTree>();
List<int> result = new List<int>();
currentLevel.Push(root);
bool leftToRight = true;
while (currentLevel.Count > 0)
{
BinaryTree temp = currentLevel.Peek();
currentLevel.Pop();
if (temp != null)
{
//same as print

if (leftToRight)
{
if (temp.Left != null)
{
nextLevel.Push(temp.Left);
}
if (temp.Right != null)
{
nextLevel.Push(temp.Right);
}
}
else
{
if (temp.Right != null)
{
nextLevel.Push(temp.Right);
}
if (temp.Left != null)
{
nextLevel.Push(temp.Left);
}
}
}
if (currentLevel.Count == 0)
{
leftToRight = !leftToRight;
Stack<BinaryTree> tempStack = currentLevel;
currentLevel = nextLevel;
nextLevel = tempStack;
}
}
return result;
}
}
public class BinaryTree
{
public BinaryTree Left { get; set; }
public BinaryTree Right { get; set; }
public int Value { get; set; }
}
}

• An example of input/output in a clearer format that a test case would be great to understand the context of your problem – IEatBagels Aug 22 '18 at 15:16

The algorithm seems okay so I'll review the OOP aspect.

## Naming

1. The method named PrintBinaryZigZag but it doesn't print anything.
2. The class named BinaryTree isn't really a binary tree, it's more of a Node.

## Implementations vs interfaces

You return List<int>, but do you really need a list?

The goal of this method if to return a list that represents a binary tree.

Should you be able to add/remove objects from this list? Do you need the indexer, that is specific to the list? I don't think so. In this case, return IEnumerable<int>.

## C# details

BinaryTree temp = currentLevel.Peek();
currentLevel.Pop();


You could simply do : BinaryTree temp = currentLevel.Pop();

## Flow

if (leftToRight)
{
if (temp.Left != null)
{
nextLevel.Push(temp.Left);
}
if (temp.Right != null)
{
nextLevel.Push(temp.Right);
}
}
else
{
if (temp.Right != null)
{
nextLevel.Push(temp.Right);
}
if (temp.Left != null)
{
nextLevel.Push(temp.Left);
}
}


I'm sure there's a way to make this smaller. Now, this is a take to maybe give you an idea, I don't think it's perfect, it's weird to use a foreach when you only have two elements in the list. But maybe if can give you an idea to make this code smaller.

var orderedNodes = leftToRight ? new []{ temp.Left, temp.Right } : new []{ temp.Right, temp.Left };

foreach(var node in orderedNodes.Where(n => n != null))
{
nextLevel.Push(node);
}


This :

if (currentLevel.Count == 0)
{
leftToRight = !leftToRight;
Stack<BinaryTree> tempStack = currentLevel;
currentLevel = nextLevel;
nextLevel = tempStack;
}


I think it could be outside your while loop.

• thanks! the last part needs to be inside the while loop otherwise you do now switch the stacks, you have 2 of those. – Gilad Aug 28 '18 at 20:20