Google

Oct 28, 2013

Java Tree structure interview questions and coding questions -- Part 2



In the previous post entitled  Java Tree structure interview questions and coding questions -- Part 1, we looked at a very simple Tree structure. In this example, let's look at a more complex tree structure with generics.

Q. Write classes for a Tripple tree structue as shown below? The Leaf contains the data, and the Node contains Leaves. Both the Leaf and Node are treated as a Tree. This is the power of composite design pattern. The example has 3 levels.


Step 1: Define the Tree interface.

package com.mycompany.flatten;

public interface Tree<T>
{

}

Step 2: Define the Leaf tree class that holds the data.

package com.mycompany.flatten;

public class Leaf<T> implements Tree<T>
{
    public static <T> Tree<T> leaf(T value)
    {
        return new Leaf<T>(value);
    }
    
    private final T data;
    
    public Leaf(T t)
    {
        this.data = t;
    }
    
    @Override
    public String toString()
    {
        return "Leaf [data=" + data + "]";
    }
    
}

Step 3: The Node tree class that holds other Leaves.

package com.mycompany.flatten;

public class Node<T> implements Tree<T>
{
    
    public static <T> Tree<T> tree(T left, T middle, T right)
    {
        return new Node<T>(Leaf.leaf(left), Leaf.leaf(middle), Leaf.leaf(right));
    }
    
    private final Triple<Tree<T>> branches;
    
    public Node(Tree<T> left, Tree<T> middle, Tree<T> right)
    {
        this.branches = new Triple<Tree<T>>(left, middle, right);
    }
    
    
    @Override
    public String toString()
    {
        return "Node {branches=" + branches + "}";
    }
    
}


Step 4: Finally, a test class that constructs the above tree structure.

package com.mycompany.flatten;

public class SpecialTreeTest
{
    
    public static void main(String[] args)
    {
        
        Tree<String> leafB21 = Leaf.leaf("B21");
        Tree<String> leafB22 = Leaf.leaf("B22");
        Tree<String> leafB23 = Leaf.leaf("B23");
        
        //takes all 3 args as "Leaf<String>" and returns "Tree<Leaf<String>>"
        Tree<Tree<String>> level3 = Node.tree(leafB21, leafB22, leafB23); // all leaves
        
        Tree<String> leafB1 = Leaf.leaf("B1");
        Tree<String> leafB3 = Leaf.leaf("B3");
        
        //takes  3 args as "Leaf<String>", "Tree<Leaf<String>>", and  "Leaf<String>" 
        Tree<Tree<? extends Object>> level2 = Node.tree(leafB1, level3, leafB3);
        
        
        Tree<Tree<? extends Object>> level1 = Node.tree(Leaf.leaf("A"), level2, Leaf.leaf("C"));
        
        System.out.println(level1); //level1 is the root

        
    }
    
}


Step 5: Finally, the output is:

Node {branches=Triple [l=Leaf [data=Leaf [data=A]], m=Leaf [data=Node {branches=Triple [l=Leaf [data=Leaf [data=B1]], m=Leaf [data=Node {branches=Triple [l=Leaf [data=Leaf [data=B21]], m=Leaf [data=Leaf [data=B22]], r=Leaf [data=Leaf [data=B23]]]}], r=Leaf [data=Leaf [data=B3]]]}], r=Leaf [data=Leaf [data=C]]]}

You may also like:

Labels: , ,

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home