.NET and me Coding dreams since 1998!

16Aug/071

Design patterns in real world use case scenarios – Composite (part 2)

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

image

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:

image

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

image

Problem solved!

To download source code click here: Example source code

Comments (1) Trackbacks (0)
  1. You’re images are broken…

    Would you hire that person?


Leave a comment

No trackbacks yet.