Check if a tree with the following structure contains a linked list:
Given the following tree:
- AA
- B2
- S1
- B1
And the following linked list:
AA –> B2 –> S1
Test:
[TestMethod]
public void TestTreeContainsLInkedlist()
{
var tree = new Node("");
var aaNode = new Node("AA");
var b2Node = new Node("B2");
b2Node.Add(new Node("S1"));
aaNode.Add(b2Node);
tree.Add(aaNode);
tree.Add(new Node("B1"));
var lInkedItem = new LinkedItem("AA", new LinkedItem("B2", new LinkedItem("S1", null)));
bool contains = TreeContainsLinkedList.Contains(tree, lInkedItem);
Assert.IsTrue(contains);
var tree1 = new Node("");
tree1.Add(new Node("KK"));
bool doesntContain = TreeContainsLinkedList.Contains(tree1, lInkedItem);
Assert.IsFalse(doesntContain);
}
Solution:
public class TreeContainsLinkedList
{
public static bool Contains(Node tree, LinkedItem linkedItem)
{
LinkedItem currentLinkedItem = linkedItem;
Node currentNode = tree;
while (currentLinkedItem != null)
{
bool exist = false;
foreach (Node node1 in currentNode)
{
if (node1.Name == currentLinkedItem.Name)
{
exist = true;
currentNode = node1;
break;
}
}
if (!exist)
{
return false;
}
currentLinkedItem = currentLinkedItem.Link;
}
return true;
}
}
public class Node : List<Node>
{
private readonly string name;
public Node(string name)
{
this.name = name;
}
public string Name
{
get { return name; }
}
}
public class LinkedItem
{
private readonly string name;
private readonly LinkedItem link;
public LinkedItem(string name, LinkedItem link)
{
this.name = name;
this.link = link;
}
public string Name
{
get { return name; }
}
public LinkedItem Link
{
get { return link; }
}
}
Comments
Post a Comment