00: Tree from a list & flattening it back to a list in Java

Hierarchical data with parent & child relationships are very common, and Java collection does not have a Tree data structure, hence it is a popular interview question. Further questions include tree data structure processing using recursiion & iteration. A Tree data structure can be represented as shown below.

Step 1: A simple Node.java class that encapsulates its value, parent node id & if any child nodes. It is important that “parent” is not included in the toString(..) method as it leads to Stack Overflow error due to recursive calls.

Tree from a list & flatten tree to list

Create a Tree from a flat list

Step 2: The main class that creates a flat list of “Nodes” first, and the Node class has child and parent ids as a flat list. Then creates a tree structure via createTree(List nodes). A root node is the top level node without a parent (i.e. parent is null).

Output:

Flatten a Tree to a list using Recursion

flatten(……)” method uses recursion to traverse a tree. Recursion is explained in detail at Iteration Vs Recursion. If you don’t have a proper stop or exit condition for a recursion, you will get a StackOverflowException.

Output:

It is important to understand that a recursion needs to have:

A Stop Condition or Exit Condition – the function returns a value when a certain condition is satisfied, without a further recursive call. If not you will get Stack Overflow Exception due to endless recursion.

The Recursive Call – the function calls itself with an input which is a step closer to the stop condition

It is also important to understand the possibility of StackOverflowException for large recursions. Tail recursion to the rescue – Recursion Vs. Tail Recursion

Flatten a Tree to a list using a while Loop instead of recursion

java.util.Deque represents a double ended queue, meaning a queue where you can add and remove elements from both ends of the queue. What makes a deque different is the unrestrictive nature of adding and removing items. In the below code, ArrayDeque will be used as a LIFO (i.e. Last In First Out) data structure (i.e. a Stack).

Flatten Tree with ArrayDeque LIFO

Output:

Learn more about Tree data structure step by step with diagrams & code.

Tags:

Java Developer & Architect Interview Q&As

Java & Big Data Tutorials

Prepare to fast-track & go places

FAQs are marked with 🔥 as some questions are not only more popular with the interviewers, but also required to build robust systems. If you are an interviewer, cover well rounded topics to judge real experience.

Don't be overwhelmed by the number of questions as the technology stacks are so vast. The quality of the answers you provide to some of the key technical & open-ended questions along with your soft skills & attitude will go a long way in getting the job offers.

Note: Some Q&As belong to more than one category.
Top