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:
- Java Tree structure interview questions and coding questions -- Part 1
- Java Tree structure interview questions and coding questions -- Part 3
- Java Tree structure interview questions and coding questions -- Part 4
Labels: Coding, DataStructure, Tree structure
0 Comments:
Post a Comment
Subscribe to Post Comments [Atom]
<< Home