To get a detail explanation of what this pattern stands for check out the Armen's blog - Composite where he posted detail article about pattern illustrated with one nice example
How this could get you a job
An usual question on job interviews could be "write a pseudo code for binary tree" (Family tree is the same tree as binary tree but not restricted to two child tree nodes as binary tree is)
I believe this is a very good interview question which would classify a developer knowledge in next 4 categories:
a) Not able to solve the problem -
b) Able to solve it using plain old recursion structural methods
c) Uses OOP techniques such as defining separate properties for child nodes of the same type
d) Deliberate using of the composite pattern
I wouldn't hire a), would hire b) as junior, c) as senior, d) as possible tech lead
Problem - use case
"Write a code which would in a given binary tree find a desired tree node and write a search traversal path."
Why composite pattern?
If we would take a look at previous composite post Composite pattern - Control tree persistence, rule of thumb there is:
Usage of composite pattern is usually appropriate whenever there are hierarchical tree structures where all the tree nods are of the same type.
Well, sound like our case
Problem - solution example
Class Diagram of the solution
Tree node code example
Every node would have a NodeKey and Node Value properties. Every node would also have a collection property which would contain instances of his own type
Something like this:
public class TreeNode
{
private readonly IList<TreeNode> _treeNodes = new List<TreeNode>();
private string _nodeKey;
private string _nodeValue;
/// <summary>
/// Initializes a new instance of the TreeNode class.
/// </summary>
/// <param name="nodeKey"></param>
/// <param name="nodeValue"></param>
public TreeNode(string nodeKey, string nodeValue)
{
_nodeKey = nodeKey;
_nodeValue = nodeValue;
}
public IList<TreeNode> TreeNodes
{
get { return _treeNodes; }
}
/// <summary>
///
/// </summary>
public string NodeKey
{
get { return _nodeKey; }
set { _nodeKey = value; }
}
public string NodeValue
{
get { return _nodeValue; }
set { _nodeValue = value; }
}
}
Required functionality implementation
Is very simple with the pattern set up like explained: TreeNode would define a method which would call the same method on all the children nodes contained in TreeNodes property.
Something like this:
public TreeNode FindByKey(string searchNodeKey, ref string resultpath)
{
if (NodeKey == searchNodeKey)
return this;
foreach (TreeNode node in TreeNodes)
{
resultpath += " -> " + node._nodeKey;
TreeNode result = node.FindByKey(searchNodeKey, ref resultpath);
if (result != null)
return result;
}
return null;
}
Testing the solution
Now when our little tree node is been written we have to test the solution.
Setting up the test tree
First we need to build a tree of nodes, something like this:
private static TreeNode buildingTheTree()
{
TreeNode rootNode=new TreeNode("rootKey","rootValue");
TreeNode firstlevelNode1 = new TreeNode("key1_1", "value1_1");
TreeNode firstlevelNode2 = new TreeNode("key1_2", "value1_2");
TreeNode secondLevellevelNode1 = new TreeNode("key2_1", "value2_1");
TreeNode thirdLevellevelNode1 = new TreeNode("key3_1", "value3_1");
TreeNode thirdLevellevelNode2 = new TreeNode("key3_2", "value3_2");
secondLevellevelNode1.TreeNodes.Add(thirdLevellevelNode1);
secondLevellevelNode1.TreeNodes.Add(thirdLevellevelNode2);
firstlevelNode1.TreeNodes.Add(secondLevellevelNode1);
rootNode.TreeNodes.Add(firstlevelNode1);
rootNode.TreeNodes.Add(firstlevelNode2);
return rootNode;
}
As you can see from the code above we pick a test case where root node, has two child nodes and first child node has his own child which has two child nodes of it's own.
Diagram of the code above result could look like this:
Testing tree functionality
Our test would be to find nodes 3_2 and Node 2_1. The code using our tree node class to achieve this could be like this
static void Main(string[] args)
{
TreeNode rootNode=buildingTheTree();
TreeNode node;
string resultPath;
resultPath=String.Empty;
node = rootNode.FindByKey("key3_2", ref resultPath);
Console.WriteLine("\nFound node key is:{0}, value is:{1}. \n SearchPath:{2}",node.NodeKey, node.NodeValue, resultPath);
resultPath=String.Empty;
node = rootNode.FindByKey("key2_1",ref resultPath);
Console.WriteLine("\nFound node key is:{0}, value is:{1}. \n SearchPath:{2}", node.NodeKey, node.NodeValue, resultPath);
Console.WriteLine("\nPress enter when you are done.");
Console.ReadLine();
}
The result
Problem solved!
To download source code click here: Example source code