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

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:

• Java Tree structure interview questions and coding questions -- Part 1
• Java Tree structure interview questions and coding questions -- Part 2
• Java Tree structure interview questions and coding questions -- Part 4