All Tree Paths Non-Recursively, by Facebook

Problem today comes from Daily Coding Problem:

Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given a binary tree, return all paths from the root to leaves.

For example, given the tree

   1
  / \
 2   3
    / \
   4   5

it should return [[1, 2], [1, 3, 4], [1, 3, 5]].

The recursive solution is relatively straightforward, so here I decided to do the non-recursive version of it. Sometimes it is important to implement the non-recursive solution in real application to avoid getting bounded by the stack memory limits, which in most languages is bounded at 1MB.
The non-recursive solution I chose uses a Stack, but it could have been done in this case with a Queue too.
Create a structure (class) holding a node and a path, push the root, when you pop check whether you're at a leaf node, if so add the current list to the return variable, and then push the children if they exist.
Solves the problem well, code below, cheers, Marcelo.

class DailyCodingProblem01022019

{
	public IList> AllPaths(Tree node)
	{
		if (node == null) return new List>();

		List> retVal = new List>();
		Stack stack = new Stack();

		stack.Push(new StackItem2(node, new List()));
		while (stack.Count > 0)
		{
			StackItem2 si2 = (StackItem2)stack.Pop();

			//Found leaf, end of path
			if (si2.node.left == null && si2.node.right == null)
			{
				si2.path.Add(si2.node.val);
				retVal.Add(si2.path);

				continue;
			}

			if (si2.node.left != null)
			{
				List leftPath = si2.path.ToList();
				leftPath.Add(si2.node.val);
				StackItem2 lsi2 = new StackItem2(si2.node.left, leftPath);
				stack.Push(lsi2);
			}
			if (si2.node.right != null)
			{
				List rightPath = si2.path.ToList();
				rightPath.Add(si2.node.val);
				StackItem2 rsi2 = new StackItem2(si2.node.right, rightPath);
				stack.Push(rsi2);
			}
		}

		return retVal;
	}
}

class StackItem2
{
	public Tree node;
	public List path;

	public StackItem2(Tree node, List path)
	{
		this.node = node;
		this.path = path;
	}
}