When to use which Java collection or data structure? and why?

List, Set, Map, and Queue(access the ends FIFO or LIFO) are the basic Java data structure interfaces for which there are different implementations to cater for different usage patterns. Java data structure interview questions are very popular, and pays to know the differences.

#1 Array (Employee[]) Vs List (List<Employee>): 

• Array is a fixed length data structure whilst a List is a variable length Collection class.
• java.util.Arrays has the helper classes for the arrays and java.util.Collections has the helper classes for the Collection classes.
• An array can use primitive data types, but the Collection classes can only use objects. 

Q. Which one to favor/use?
A. Favor  List.

• Arrays are inflexible and do not have the expressive power of generic types.  
• List gives you the data abstraction as you can swap ArrayList, LinkedList, CopyOnWriteArrayList, etc depending on the requirements.
• List allows you to add and subtract elements even it is an O(n) operation in worst case scenario.

#2: ArrayList (ArrayList<employee>)Vs LinkedList (LinkedList<employee>)

• Insertions and deletions are faster in LinkedList compared to an ArrayList as LinkedList uses links (i.e. before and next reference) as opposed to an ArrayList, which uses an array under the covers, and may need to resize the array if the array gets full.  Adding to an ArrayList has a worst case scenario of O(n) whilst LinkedList has O(1). 
• LinkedList has more memory footprint than ArrayList. An ArrayList only holds actual object whereas LinkedList holds both data and reference of next and previous node.  
• Random access has the worst case scenario of O(n) in LinkedList as to access 6th element in a LinkedList with 8 elements, you need to traverse through 1 to 5th element before you can get to the 6th element, whereas in an ArrayList, you can get the 6th element with O(1) with list.get(5). 

Q. Which one to favor/use?
A. Almost always favor an ArrayList. ArrayLists are good for write once and randomly read many times, and for adding elements at the end, but bad at add/remove from the front or middle. LinkedLists are useful in rare usage patterns where insertion and deletion in the front and middle is significantly more than the retrievals, and the LinkedList can live with the O(n) cost of random access.

If you are after adding/removing from both ends, ArrayDeque is better than a LinkedList. The Deque interface is pronounced as "deck", and represents a double-ended queue. ArrayDeque is backed by an array. ArrayDeque can be used as both a Queue (i.e. FIFO) and a Stack (i.e. LIFO). ArrayDeque performs better than LinkedList, as  ArrayDeque is backed by an array and Array is more cache friendly. Also, ArrayDeque is more memory efficient than LinkedList since it does not have to keep an additional reference to previous or next node. ArrayDeque does not take null elements, but a LinkedList does. The best operation in a LinkedList implementation is removing the current element during the iteration. LinkedList implementations are also not ideal to iterate. So, LinkedList is very rarely used.


#3: List Vs Set

Set can't have duplicates whereas a List can have duplicates.

#4: HasMap Vs TreeMap

TreeMap is an implementation of a SortedMap, where the order of the keys can be sorted, and when iterating over the keys, you can expect that keys will be in order. HashMap on the other hand, makes no such guarantee on the order.

Q. Which one to favor/use?
A. In general, favor HashMap as it is more efficient in general, and use a Comparator to sort when required. Use a TreeMap only when it is required to keep the keys in a sorted order to iterate over them.


#5: HashSet, ArrayList Vs. CopyOnWriteSet, CopyOnWriteArrayList

HashSet and ArryList are not thread-safe and you need to provide your own synchronization, whereas CopyOnWriteArraySet and CopyOnWriteArrayList are not only thread-safe, but more efficient as they allow concurrent multiple  reads and single write. This concurrent read and write behavior is accomplished by  making a brand new copy of the list every time it is altered.

Q. Which one to favor/use?
A. Favor CopyOnWriteArraySet or CopyOnWriteArrayList only when the number of reads is significantly more than the number of writes. It also gives you fail safe iteration when you want to add/remove elements during iteration.


#6: HashMap Vs ConcurrentHashMap

HashMap is not thread-safe and you need to provide your own synchronization with Collections.synchornizedMap(hashMap), which will return a collection which is almost equivalent to the legacy Hashtable, where every modification operation on Map is locked. As the name implies, ConcurrentHashMap provides thread-safety by dividing the whole map into different partitions based upon concurrency level and locking only particular portion instead of locking the whole map.  ConcurrentHashMap does not allow NULL key values, whereas HashMap there can only be one null key.

Q. Which one to favor/use?
A. Favor ConcurrentHashMap  for scalability.


#7: new SynchronousQueue( ) Vs. new ArrayBlockingQueue(1) or LinkedBlockingQueue(1)


SynchronousQueue is a queue that can only contain a single element internally. A thread inserting an element into a SynchronousQueue blocked until another thread takes that element from the queue. Similarly, if a thread tries to take an element, and no element is currently present, that thread will be blocked until a thread inserts an element into the SynchronousQueue.

SynchronousQueue provides extremely good throughput when compared to a unit sized ArrayBlockingQueue(1) or LinkedBlockingQueue(1). SynchronousQueue  is the default BlockingQueue used in the Executor framework for the Executors.newCachedThreadPool( ).


Q. Which one to favor/use?
A.

• Use SynchronousQueue in scenarios where a task to be executed asynchronously while discarding any further requests until the task is finished. 

• executor = new ThreadPoolExecutor(
      1, 1, 
      2000, TimeUnit.SECONDS, 
      new SynchronousQueue<runnable>(),
      new ThreadPoolExecutor.DiscardPolicy());
  

• Use SynchronousQueue to improve application performance. 

#8: HashMap Vs LinkedHashMap

LinkedHashMap will iterate in the order in which the entries were put into the map. HashMap does not provide any grantees about the iteration order.



Q. What is a BlockingQueue?
A. BlockingQueue is a Queue that supports additional operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element. The main advantage is that a BlockingQueue is that it provides a correct, thread-safe implementation with  throttling.

• The producers are throttled to add elements if the consumers get too far behind. 
• If the Queue capacity is limited, the memory consumption will be limited as well. 

Q. Why Vector, Stack, and Hashtable are legacy data structures and not to be used?
A. All methods in these classes are synchronized (i.e. coarse grained lock), hence not efficient. Favor the concurrent data structures for concurrent read and single write.

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

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

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

Java Tree finding the Lowest Common Ancestor (LCA)

This extends Java Preorder Tree Traversal : recursive and iterative flattening of tree. This is also a very popular coding interview question.

Q. Find out the LCA (i.e. Lowest Common Ancestor) for nodes a and b where a = 3 and b = 4 as shown below?

A. The Node a has ancestors : 2 and 1.  The Node b has ancestors 2 and 1. The Lowest Common Ancestor is Node with value 2. Let's look at the code for this.


Step 1: Define the TreeNode class as did before but define the "parent" attribute so that each node knows not only who the children are, but also who the parent is as well.

 
package com.mycompany.app14;

public class TreeNode
{
    
    private int value;
    //children
    private TreeNode left;
    private TreeNode right;
    //parent
    private TreeNode parent;
    
    public TreeNode(int value, TreeNode left, TreeNode right)
    {
        super();
        this.value = value;
        this.left = left;
        this.right = right;
    }
    
    public int getValue()
    {
        return value;
    }
    
    public void setValue(int value)
    {
        this.value = value;
    }
    
    public TreeNode getLeft()
    {
        return left;
    }
    
    public void setLeft(TreeNode left)
    {
        this.left = left;
    }
    
    public TreeNode getRight()
    {
        return right;
    }
    
    public void setRight(TreeNode right)
    {
        this.right = right;
    }
    
    public TreeNode getParent()
    {
        return parent;
    }
    
    public void setParent(TreeNode parent)
    {
        this.parent = parent;
    }
    
    @Override
    public String toString()
    {
        return "TreeNode [value=" + value + ", left=" + left + ", right=" + right + "]";
    }  
}

Step 2: The test class that constructs the tree structure and then calculates the LCA. Uses a Deque class, which is a LIFO structure.

 
package com.mycompany.app14;

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

public class TestFindCommonAncestor
{
    
    public static void main(String[] args)
    {
        TreeNode root = createOneTo6PreOrderTree();
        
        //Find the common ancestor for two given nodes a and b.
        
        //root node value is 1, node a is 3, and node b is 4
        //so, find the Least Common Ancestor for nodes representing values 3 and 4
        TreeNode commonNode = findLowestCommonAncestor(root.getLeft().getLeft(), root.getLeft().getRight());
        System.out.println(commonNode);
        
    }
    
    private static TreeNode createOneTo6PreOrderTree()
    {
        TreeNode leaf3 = new TreeNode(3, null, null);
        TreeNode leaf4 = new TreeNode(4, null, null);
        TreeNode leaf6 = new TreeNode(6, null, null);
        
        TreeNode node5 = new TreeNode(5, leaf6, null);
        TreeNode node2 = new TreeNode(2, leaf3, leaf4);
        
        TreeNode root1 = new TreeNode(1, node2, node5);
        
        //set parents
        leaf3.setParent(node2);
        leaf4.setParent(node2);
        
        leaf6.setParent(node5);
        
        node2.setParent(root1);
        node5.setParent(root1);
        
        return root1;
    }
    
    /**
     * @param a
     * @param b
     * @return
     */
    public static TreeNode findLowestCommonAncestor(TreeNode a, TreeNode b)
    {
        TreeNode oldNode = null;
        
        //find the parent nodes of a: should have 1, 2, and 3 for a = 3 
        Deque<TreeNode> parentNodesA = new ArrayDeque<TreeNode>();
        while (a != null)
        {
            parentNodesA.push(a);
            a = a.getParent();
        }
        
        //find the parent nodes of b: should have 1, 2 and 4 for b = 4
        Deque<TreeNode> parentNodesB = new ArrayDeque<TreeNode>();
        while (b != null)
        {
            parentNodesB.push(b);
            b = b.getParent();
        }
        
        //initially a and b will be null
        while (a == b && !parentNodesA.isEmpty() && !parentNodesB.isEmpty())
        {
            oldNode = a;
            a = parentNodesA.pop();
            b = parentNodesB.pop();
        }
        
        // a will be 3 and b will be 4 and oldNode will be 2
        if (a == b)
        {
            return a;                        // One node is descended from the other
        }
        else
        {
            return oldNode;                 // Neither is descended from the other
        }
        
    }
}

Step 3: Output

 
TreeNode [value=2, left=TreeNode [value=3, left=null, right=null], right=TreeNode [value=4, left=null, right=null]]

Java Preorder Tree Traversal : recursive and iterative flattening of tree

Core Java Coding Questions and Answers for beginner to intermediate level

Q1

Q2

Q3

Q4

Q5

Q6

The Logic and Datastructure Essentials chapter of my book "Core Java Career Essentials" covered a lot of questiomns and answers on different data structures and where to use them with lots of diagrams and code snippets. This blog post covers just the  Preorder Tree Traversal with code snippets. The preorder tree structure is a very popular Java coding interview question:

The left nodes are traversed before the right nodes.

Q. How will you fltten a preorder tree in Java?
A.

Step 1: The TreeNode class can be decalred as shown below.

 
package com.mycompany.app14;

public class TreeNode
{
    private int value;
    private TreeNode left;
    private TreeNode right;
    
    public TreeNode(int value, TreeNode left, TreeNode right)
    {
        super();
        this.value = value;
        this.left = left;
        this.right = right;
    }
    
    public int getValue()
    {
        return value;
    }
    
    public void setValue(int value)
    {
        this.value = value;
    }
    
    public TreeNode getLeft()
    {
        return left;
    }
    
    public void setLeft(TreeNode left)
    {
        this.left = left;
    }
    
    public TreeNode getRight()
    {
        return right;
    }
    
    public void setRight(TreeNode right)
    {
        this.right = right;
    }
    
}

Step 2: Test class to construct the tree structure using the TreeNode class and traverse the tree bothe recursively and iteratively to printhe values in the Preorder.

 
package com.mycompany.app14;

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

public class Test
{
    public static void main(String[] args)
    {
        TreeNode root = createOneTo6PreOrderTree();
        printTreeRecursively(root);
        System.out.println("---------------------------------");
        printTreeIteratively(root);
    }
    
    private static TreeNode createOneTo6PreOrderTree()
    {
        TreeNode leaf3 = new TreeNode(3, null, null);
        TreeNode leaf4 = new TreeNode(4, null, null);
        TreeNode leaf6 = new TreeNode(6, null, null);
        
        TreeNode node5 = new TreeNode(5, leaf6, null);
        TreeNode node2 = new TreeNode(2, leaf3, leaf4);
        
        TreeNode root1 = new TreeNode(1, node2, node5);
        
        return root1;
    }
    
    /**
     * traverse the tree recursively and print
     * 
     * @param TreeNode node
     */
    private static void printTreeRecursively(TreeNode node)
    {
        //Exit condition for recursion 
        if (node == null)
        {
            return;
        }
        
        System.out.println(node.getValue());
        
        printTreeRecursively(node.getLeft());     //recurse left node 
        printTreeRecursively(node.getRight());    //recurse right node
        
    }
    
    /**
     * Achieved using a Deque (LIFO)
     * 
     * @param TreeNode node
     */
    private static void printTreeIteratively(TreeNode node)
    {
        Deque<TreeNode> s = new ArrayDeque<TreeNode>(6);
        s.push(node);  // push the root node
        
        while (!s.isEmpty())
        {
            node = s.pop();
            System.out.println(node.getValue());
            
            //stack is LIFO, so push the right node first
            if (node.getRight() != null)
            {
                s.push(node.getRight());
            }
            
            //stack is LIFO, so push the left node last
            if (node.getLeft() != null)
            {
                s.push(node.getLeft());
            }
        }
        
    }
}

Step 3: The iterative approach represented diagramatucally for better understanding. Shows how the numbers are pushed and popped.

Step 4: Output

 
1
2
3
4
5
6
---------------------------------
1
2
3
4
5
6