Tree Contains LinkedList

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