This is an extension to
Java Tree structure interview questions and coding questions -- Part 2, and adds
functional programming and
recursion.
Step 1: The
Tree interface with
get( ) method that returns either a
Triple tree or
Leaf data.
package com.mycompany.flatten;
public interface Tree<T>
{
abstract Either<T, Triple<Tree<T>>> get();
}
Step 2: The
Leaf that implements the
Tree interface.
package com.mycompany.flatten;
public class Leaf<T> implements Tree<T>
{
private final T data;
public static <T> Tree<T> leaf(T value)
{
return new Leaf<T>(value);
}
public Leaf(T t)
{
this.data = t;
}
public T getData()
{
return data;
}
@SuppressWarnings("unchecked")
public Either<T, Triple<Tree<T>>> get()
{
return Either.left(data);
}
@Override
public String toString()
{
return "Leaf [data=" + data + "]";
}
}
Step 3: The
Node with
Triple tree that implements the
Tree interface.
package com.mycompany.flatten;
public class Node<T> implements Tree<T>
{
private final Triple<Tree<T>> branches;
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));
}
public Node(Tree<T> left, Tree<T> middle, Tree<T> right)
{
this.branches = new Triple<Tree<T>>(left, middle, right);
}
public Either<T, Triple<Tree<T>>> get()
{
return Either.right(branches);
}
public Triple<Tree<T>> getBranches()
{
return branches;
}
@Override
public String toString()
{
return "Node {branches=" + branches + "}";
}
}
Step 4: The
Triple class used by the
Node.
package com.mycompany.flatten;
/**
* A type that stores three values of the same type.
*/
public class Triple<T>
{
private final T left, middle, right;
public Triple(T l, T m, T r)
{
this.left = l;
this.middle = m;
this.right = r;
}
public T left()
{
return left;
}
public T middle()
{
return middle;
}
public T right()
{
return right;
}
@Override
public String toString()
{
return "Triple [l=" + left + ", m=" + middle + ", r=" + right + "]";
}
}
Step 5: As you can see that the Node and Leaf are using the class Either to handle Node and Leaf differently. The Either stores left or right values but not both. The Leaf uses the left and the Node uses the right. You can pass in a Function to be executed for the leaf and node.
package com.mycompany.flatten;
/**
* X type which stores one of either of two types of value, but not both.
*/
public class Either<X, Y>
{
private final X x;
private final Y y;
private Either(X x, Y y)
{
this.x = x;
this.y = y;
}
/**
* Constructs x left-type Either
*/
public static <X> Either left(X x)
{
if (x == null)
throw new IllegalArgumentException();
return new Either(x, null);
}
/**
* Constructs x right-type Either
*/
public static <Y> Either right(Y y)
{
if (y == null)
throw new IllegalArgumentException();
return new Either(null, y);
}
/**
* Applies function f to the contained value if it is x left-type and
* returns the result.
*/
public void ifLeft(Function<X> f)
{
if (!this.isLeft())
{
throw new IllegalStateException();
}
f.apply(x);
}
/**
* Applies function f to the contained value if it is x right-type and
* returns the result.
*/
public void ifRight(Function<Y> f)
{
if (this.isLeft())
{
throw new IllegalStateException();
}
f.apply(y);
}
/**
* @return true if this is x left, false if it is x right
*/
public boolean isLeft()
{
return y == null;
}
@Override
public String toString()
{
return "Either [x=" + x + ", y=" + y + "]";
}
}
Step 6: Define the
Function interface
package com.mycompany.flatten;
public interface Function<P>
{
void apply(P p);
}
Step 7: Define two different implementations for the
Function.
LeafPrint and
NodePrint for printing
Leaf and
Node respectively.
package com.mycompany.flatten;
public class LeafPrint<P> implements Function<P>
{
public void apply(P p)
{
System.out.println("--> Leaf:" + p);
}
}
package com.mycompany.flatten;
public class NodePrint<P> implements Function<P>
{
public void apply(P p)
{
Triple t = (Triple<P>) p;
System.out.println("left ==> " + t.left() + " || middle ==> " + t.middle() + " || right ==> " + t.right());
}
}
Step 8: The
FlattenTree interface that works on the
Tree.
package com.mycompany.flatten;
public interface FlattenTree<T>
{
void flatten(Tree<T> tree);
}
Step 9: Implementation of
FlattenTree interface
RecursiveFlattenTree.
package com.mycompany.flatten;
public class RecursiveFlattenTree<T> implements FlattenTree<T>
{
public void flatten(Tree<T> tree)
{
if (tree == null)
{
return;
}
Either<T, Triple<Tree<T>>> either = tree.get();
if (either.isLeft())
{
either.ifLeft(new LeafPrint<T>());
}
else
{
either.ifRight(new NodePrint<Triple<Tree<T>>>());
Triple<Tree<T>> trippleTree = ((Node<T>) tree).getBranches();
flatten(trippleTree.left()); // recursion
flatten(trippleTree.middle()); // recursion
flatten(trippleTree.right()); // recursion
}
}
}
Step 10: Finally, the
SpecialTreeTest test class with main method.
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);
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<String>> level2 = new Node(leafB1, level3, leafB3);
Tree<Tree<String>> level1 = new Node(Leaf.leaf("A"), level2, Leaf.leaf("C"));
//System.out.println(level1); //level1 is the root
FlattenTree<Tree<String>> flatTree = new RecursiveFlattenTree<Tree<String>>();
flatTree.flatten(level1);
}
}
The ouput
left ==> Leaf [data=A] || middle ==> Node {branches=Triple [l=Leaf [data=B1], m=Node {branches=Triple [l=Leaf [data=Leaf [data=B21]], m=Leaf [data=Leaf [data=B22]], r=Leaf [data=Leaf [data=B23]]]}, r=Leaf [data=B3]]} || right ==> Leaf [data=C]
--> Leaf:A
left ==> Leaf [data=B1] || middle ==> Node {branches=Triple [l=Leaf [data=Leaf [data=B21]], m=Leaf [data=Leaf [data=B22]], r=Leaf [data=Leaf [data=B23]]]} || right ==> Leaf [data=B3]
--> Leaf:B1
left ==> Leaf [data=Leaf [data=B21]] || middle ==> Leaf [data=Leaf [data=B22]] || right ==> Leaf [data=Leaf [data=B23]]
--> Leaf:Leaf [data=B21]
--> Leaf:Leaf [data=B22]
--> Leaf:Leaf [data=B23]
--> Leaf:B3
--> Leaf:C
You may also like:
