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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
import java.util.ArrayList; import java.util.List; public class Node { private String id; //Current node id, Example: 2 private String parentId; //Parent node id, Example: 1 private String value; // Example: Two private Node parent; private List<Node> children; //Example: Nodes with IDs 3 & 4 public Node() { super(); this.children = new ArrayList<>(); } public Node(String value, String childId, String parentId) { this.value = value; this.id = childId; this.parentId = parentId; this.children = new ArrayList<>(); } public String getValue() { return value; } public void setValue(String value) { this.value = value; } public String getId() { return id; } public void setId(String id) { this.id = id; } public String getParentId() { return parentId; } public void setParentId(String parentId) { this.parentId = parentId; } public Node getParent() { return parent; } public void setParent(Node parent) { this.parent = parent; } public List<Node> getChildren() { return children; } public void setChildren(List<Node> children) { this.children = children; } public void addChild(Node child) { if (!this.children.contains(child) && child != null) this.children.add(child); } @Override public String toString() { return "Node [id=" + id + ", parentId=" + parentId + ", value=" + value + ", children=" + children + "]"; } } |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * * Tree to be created * 1 --> 2 * --> 3 * --> 4 --> 5 * */ public class ListToTree { public static void main(String[] args) { //Create a List of nodes Node node1 = new Node("Five", "5", "4"); Node node2 = new Node("Four", "4", "2"); Node node3 = new Node("Two", "2", "1"); Node node4 = new Node("Three", "3", "2"); Node node5 = new Node("One", "1", null); // root as parentId is null List<Node> nodes = new ArrayList<>(); nodes.add(node1); nodes.add(node2); nodes.add(node3); nodes.add(node4); nodes.add(node5); //convert to a tree createTree(nodes); } private static void createTree(List<Node> nodes) { Map<String, Node> mapTmp = new HashMap<>(); //Save all nodes to a map for (Node current : nodes) { mapTmp.put(current.getId(), current); } //loop and assign parent/child relationships for (Node current : nodes) { String parentId = current.getParentId(); if (parentId != null) { Node parent = mapTmp.get(parentId); if (parent != null) { current.setParent(parent); parent.addChild(current); mapTmp.put(parentId, parent); mapTmp.put(current.getId(), current); } } } //get the root Node root = null; for (Node node : mapTmp.values()) { if(node.getParent() == null) { root = node; break; } } System.out.println(root); } } |
Output:
|
1 2 3 4 |
Node [id=1, parentId=null, value=One, children=[Node [id=2, parentId=1, value=Two, children=[Node [id=4, parentId=2, value=Four, children=[Node [id=5, parentId=4, value=Five, children=[]]]], Node [id=3, parentId=2, value=Three, children=[]]]]]] |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * * Tree to be created * 1 --> 2 * --> 3 * --> 4 --> 5 * */ public class ListToTree { public static void main(String[] args) { Node node1 = new Node("Five", "5", "4"); Node node2 = new Node("Four", "4", "2"); Node node3 = new Node("Two", "2", "1"); Node node4 = new Node("Three", "3", "2"); Node node5 = new Node("One", "1", null); List<Node> nodes = new ArrayList<>(); nodes.add(node1); nodes.add(node2); nodes.add(node3); nodes.add(node4); nodes.add(node5); createTree(nodes); } private static void createTree(List<Node> nodes) { Map<String, Node> mapTmp = new HashMap<>(); //Save all nodes to a map for (Node current : nodes) { mapTmp.put(current.getId(), current); } //loop and assign parent/child relationships for (Node current : nodes) { String parentId = current.getParentId(); if (parentId != null) { Node parent = mapTmp.get(parentId); if (parent != null) { current.setParent(parent); parent.addChild(current); mapTmp.put(parentId, parent); mapTmp.put(current.getId(), current); } } } //get the root Node root = null; for (Node node : mapTmp.values()) { if(node.getParent() == null) { root = node; break; } } System.out.println(root); List<Node> result = flatten(root, new ArrayList<>()); System.out.println("List size = " + result.size()); System.out.println(result); } /** * . Recursive method is used to traverse down the tree **/ private static List<Node> flatten(Node node, List<Node> flatList) { if(node != null){ Node n = new Node(node.getValue(), node.getId(), node.getParentId()); // get rid of children & parent references flatList.add(n); } List<Node> children = node.getChildren(); for (Node child : children) { if(child.getChildren() != null) { flatten(child, flatList); // Recursive call - Keep flattening until no more children } } // stop or exit condition return flatList; } } |
Output:
|
1 2 3 4 5 |
Node [id=1, parentId=null, value=One, children=[Node [id=2, parentId=1, value=Two, children=[Node [id=4, parentId=2, value=Four, children=[Node [id=5, parentId=4, value=Five, children=[]]]], Node [id=3, parentId=2, value=Three, children=[]]]]]] List size = 5 [Node [id=1, parentId=null, value=One, children=[]], Node [id=2, parentId=1, value=Two, children=[]], Node [id=4, parentId=2, value=Four, children=[]], Node [id=5, parentId=4, value=Five, children=[]], Node [id=3, parentId=2, value=Three, children=[]]] |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.HashMap; import java.util.List; import java.util.Map; /** * * Tree to be created * 1 --> 2 * --> 3 * --> 4 --> 5 * */ public class ListToTree { public static void main(String[] args) { Node node1 = new Node("Five", "5", "4"); Node node2 = new Node("Four", "4", "2"); Node node3 = new Node("Two", "2", "1"); Node node4 = new Node("Three", "3", "2"); Node node5 = new Node("One", "1", null); List<Node> nodes = new ArrayList<>(); nodes.add(node1); nodes.add(node2); nodes.add(node3); nodes.add(node4); nodes.add(node5); createTree(nodes); } private static void createTree(List<Node> nodes) { Map<String, Node> mapTmp = new HashMap<>(); // Save all nodes to a map for (Node current : nodes) { mapTmp.put(current.getId(), current); } // loop and assign parent/child relationships for (Node current : nodes) { String parentId = current.getParentId(); if (parentId != null) { Node parent = mapTmp.get(parentId); if (parent != null) { current.setParent(parent); parent.addChild(current); mapTmp.put(parentId, parent); mapTmp.put(current.getId(), current); } } } // get the root Node root = null; for (Node node : mapTmp.values()) { if (node.getParent() == null) { root = node; break; } } System.out.println(root); List<Node> result = flatten(root); System.out.println("List size = " + result.size()); System.out.println(result); } /** * . Flatten using a Deque - Double ended Queue * **/ private static List<Node> flatten(Node node) { if (node == null) { return null; } List<Node> flatList = new ArrayList<>(); Deque<Node> q = new ArrayDeque<>(); q.addLast(node); //add the root while (!q.isEmpty()) { //Keep looping until all nodes are traversed Node n = q.removeLast(); flatList.add(new Node(n.getValue(), n.getId(), n.getParentId())); List<Node> children = n.getChildren(); if (children != null) { for (Node child : children) { q.addLast(child); } } } return flatList; } } |
Output:
|
1 2 3 4 5 |
Node [id=1, parentId=null, value=One, children=[Node [id=2, parentId=1, value=Two, children=[Node [id=4, parentId=2, value=Four, children=[Node [id=5, parentId=4, value=Five, children=[]]]], Node [id=3, parentId=2, value=Three, children=[]]]]]] List size = 5 [Node [id=1, parentId=null, value=One, children=[]], Node [id=2, parentId=1, value=Two, children=[]], Node [id=3, parentId=2, value=Three, children=[]], Node [id=4, parentId=2, value=Four, children=[]], Node [id=5, parentId=4, value=Five, children=[]]] |
Learn more about Tree data structure step by step with diagrams & code.
(Visited 144 times, 5 visits today)