The Deepest Node, by Daily Coding Problem

Given a binary tree, return its deepest node

Got an article by Daily Coding Problem claiming that this was an interview question asked during a Facebook or Google interview.
The question is relatively simple, both recursively or non-recursively. Recursively can be done with a post-order traversal as demonstrated in the previous post. In this post the solution will be non-recursive.

The idea is very simple: use a stack, push the node and the level. Pop. Check for the max level. Push the children. Can be done with either a stack or a queue, it doesn't really matter. That's it!

Code is here: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem09232018.cs

Thanks, Marcelo

public class StackItem
{
public Tree tree;
public int level;

public StackItem(Tree tree, int level)
{
this.tree = tree;
this.level = level;
}
}

public int DeepestNode(Tree tree)
{
if (tree == null) return 0;

StackItem si = new StackItem(tree, 1);
Stack stack = new Stack();
stack.Push(si);
int deepestLevel = -1;
int deepestNode = 0;

while (stack.Count > 0)
{
StackItem nsi = (StackItem)stack.Pop();

if (nsi.level > deepestLevel)
{
deepestLevel = nsi.level;
deepestNode = nsi.tree.val;
}

if (nsi.tree.left != null)
{
StackItem lsi = new StackItem(nsi.tree.left, nsi.level + 1);
stack.Push(lsi);
}
if (nsi.tree.right != null)
{
StackItem rsi = new StackItem(nsi.tree.right, nsi.level + 1);
stack.Push(rsi);
}
}


return deepestNode;
}