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

This is an extension to Java Tree structure interview questions and coding questions -- Part 3 where recursion was used for FlattenTree interface. Let's use iteration here.

Step 1: The FlattenTree  interface.

package com.mycompany.flatten;

public interface FlattenTree<T>
{
    void flatten(Tree<T> tree);
}

Step 2: The iterative implementation IterativeFlattenTree. This uses a LIFO stack to push and pop Tree elements.

package com.mycompany.flatten;

import java.util.ArrayDeque;
import java.util.Deque;

public class IterativeFlattenTree<T> implements FlattenTree<T>
{
    
    public void flatten(Tree<T> tree)
    {
        
        if (tree == null)
        {
            return;
        }
        
        //use a double ended queue as a stack i.e. LIFO
        Deque<Tree<T>> q = new ArrayDeque<Tree<T>>();
        q.push(tree);
        
        while (!q.isEmpty())
        {
            tree = q.pop();
            Either<T, Triple<Tree<T>>> either = tree.get();
            
            if (!either.isLeft())
            {
                either.ifRight(new NodePrint<Triple<Tree<T>>>());
                Triple<Tree<T>> trippleTree = ((Node<T>) tree).getBranches();
                
                q.push(trippleTree.right());
                q.push(trippleTree.middle());
                q.push(trippleTree.left());
                
            }
            else
            {
                either.ifLeft(new LeafPrint<T>());
            }
            
        }
        
    }
}

Step 3: Finally, the test class with a 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"));
        
        
        FlattenTree<Tree<String>> flatTree = new IterativeFlattenTree<Tree<String>>();
        flatTree.flatten(level1);
        
    }
    
}

The output is:

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 3