All Tree Paths Non-Recursively, by Facebook
Problem today comes from Daily Coding Problem:
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
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;
}
}
Comments
Post a Comment
[γγ¬γΌγ ]