4
\$\begingroup\$

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
                    result.Add(temp.Value);

                    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; }
    }
}
\$\endgroup\$
  • \$\begingroup\$ An example of input/output in a clearer format that a test case would be great to understand the context of your problem \$\endgroup\$ – IEatBagels Aug 22 '18 at 15:16
1
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.