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.


Java developer & architect Q&As

Java developers Q&As

Top