This algorithm is to generate random tree based on max integer value. This is very useful when you want tree for your algorithm.
Here we are going to create nodes based on level.
Lets see algorithm.
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 |
public static TreeNode generateTree(int max) { int index = 1; if (max < index) { return null; } TreeNode tn = new TreeNode(); tn.value = index++; int level = 0; List<TreeNode> listOfNodesAtLevel0 = new ArrayList<>(); listOfNodesAtLevel0.add(tn); Map<Integer, List<TreeNode>> levelNodesMap = new HashMap<>(); levelNodesMap.put(level, listOfNodesAtLevel0); while (levelNodesMap.containsKey(level) && index <= max) { List<TreeNode> nodes = levelNodesMap.get(level); List<TreeNode> listOfNodesInNextLevel = new ArrayList<>(); for (TreeNode node : nodes) { int value = index++; if (value <= max) { node.leftNode = new TreeNode(); node.leftNode.value = value; node.leftNode.nodeName = String.valueOf(value); listOfNodesInNextLevel.add(node.leftNode); } value = index++; if (value <= max) { node.rightNode = new TreeNode(); node.rightNode.value = value; node.rightNode.nodeName = String.valueOf(value); listOfNodesInNextLevel.add(node.rightNode); } } ++level; if(listOfNodesInNextLevel.size() > 0) { levelNodesMap.put(level,listOfNodesInNextLevel); } } // printTree(tn); return tn; } |