Problem
I have improved the Pretty Printing of binary tree that I implemented previously. In this follow up I have made changes such that every tree is printed (not just a Complete binary tree).
Here is my changed implementation. Please suggest any improvements that are required.
public class PrettyPrintTree {
public TreeNode root;
public PrettyPrintTree(List<Integer> list) {
root = createTree(list);
}
public static class TreeNode {
TreeNode left;
TreeNode right;
int value;
public TreeNode(int value) {
this.value = value;
}
}
public static TreeNode createTree(List<Integer> list) {
TreeNode root = null;
TreeNode temp, temp2;
for (Integer integer : list) {
if (root == null) {
root = new TreeNode(integer);
root.left = null;
root.right = null;
continue;
}
temp = root;
temp2 = root;
while (temp != null) {
temp2 = temp;
temp = (temp.value < integer) ? temp.right : temp.left;
}
if (temp2.value < integer) {
temp2.right = new TreeNode(integer);
} else {
temp2.left = new TreeNode(integer);
}
}
return root;
}
private static int getMaximumHeight(TreeNode node) {
if (node == null)
return 0;
int leftHeight = getMaximumHeight(node.left);
int rightHeight = getMaximumHeight(node.right);
return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}
private static String multiplyString(String string, int times) {
StringBuilder builder = new StringBuilder(string.length() * times);
for (int i = 0; i < times; ++i) {
builder.append(string);
}
return builder.toString();
}
public static String getStartingSpace(int height) {
return multiplyString(" ", ((int) Math.pow(2, height - 1)) / 2);
}
public static String getUnderScores(int height) {
int noOfElementsToLeft = ((int) Math.pow(2, height) - 1) / 2;
int noOfUnderScores = noOfElementsToLeft
- ((int) Math.pow(2, height - 1) / 2);
return multiplyString("__", noOfUnderScores);
}
public static String getSpaceBetweenTwoNodes(int height) {
if (height == 0)
return "";
int noOfNodesInSubTreeOfNode = ((int) Math.pow(2, height - 1)) / 2;
/** Sum of spaces of the subtrees of nodes + the parent node */
int noOfSpacesBetweenTwoNodes = noOfNodesInSubTreeOfNode * 2 + 1;
return multiplyString(" ", noOfSpacesBetweenTwoNodes);
}
public static void printNodes(List<TreeNode> queueOfNodes,
int noOfNodesAtCurrentHeight, int height) {
StringBuilder nodesAtHeight = new StringBuilder();
String startSpace = getStartingSpace(height);
String spaceBetweenTwoNodes = getSpaceBetweenTwoNodes(height);
String underScore = getUnderScores(height);
String underScoreSpace = multiplyString(" ", underScore.length());
nodesAtHeight.append(startSpace);
for (int i = 0; i < noOfNodesAtCurrentHeight; i++) {
TreeNode node = (TreeNode) queueOfNodes.get(i);
if (node == null) {
nodesAtHeight.append(underScoreSpace)
.append(" ")
.append(underScoreSpace)
.append(spaceBetweenTwoNodes);
} else {
nodesAtHeight
.append(node.left != null ? underScore
: underScoreSpace)
.append(String.format("%2d", node.value))
.append(node.right != null ? underScore
: underScoreSpace)
.append(spaceBetweenTwoNodes);
}
}
System.out.println(nodesAtHeight.toString().replaceFirst("\s+$", ""));
}
public static String getSpaceBetweenLeftRightBranch(int height) {
int noOfNodesBetweenLeftRightBranch = ((int) Math.pow(2, height - 1) - 1);
return multiplyString(" ", noOfNodesBetweenLeftRightBranch);
}
public static String getSpaceBetweenRightLeftBranch(int height) {
int noOfNodesBetweenLeftRightBranch = (int) Math.pow(2, height - 1);
return multiplyString(" ", noOfNodesBetweenLeftRightBranch);
}
public static void printBranches(List<TreeNode> queueOfNodes,
int noOfNodesAtCurrentHeight, int height) {
if (height <= 1)
return;
StringBuilder brachesAtHeight = new StringBuilder();
String startSpace = getStartingSpace(height);
String leftRightSpace = getSpaceBetweenLeftRightBranch(height);
String rightLeftSpace = getSpaceBetweenRightLeftBranch(height);
brachesAtHeight
.append(startSpace.substring(0, startSpace.length() - 1));
for (int i = 0; i < noOfNodesAtCurrentHeight; i++) {
TreeNode node = queueOfNodes.get(i);
if (node == null) {
brachesAtHeight.append(" ")
.append(leftRightSpace)
.append(" ")
.append(rightLeftSpace);
} else {
brachesAtHeight.append(node.left != null ? "/" : " ")
.append(leftRightSpace)
.append(node.right != null ? "\" : " ")
.append(rightLeftSpace);
}
}
System.out
.println(brachesAtHeight.toString().replaceFirst("\s+$", ""));
}
public static void prettyPrintTree(TreeNode root) {
LinkedList<TreeNode> queueOfNodes = new LinkedList<>();
int height = getMaximumHeight(root);
int level = 0;
int noOfNodesAtCurrentHeight = 0;
queueOfNodes.add(root);
while (!queueOfNodes.isEmpty() && level < height) {
noOfNodesAtCurrentHeight = ((int) Math.pow(2, level));
printNodes(queueOfNodes, noOfNodesAtCurrentHeight, height - level);
printBranches(queueOfNodes, noOfNodesAtCurrentHeight, height
- level);
for (int i = 0; i < noOfNodesAtCurrentHeight; i++) {
TreeNode currNode = queueOfNodes.peek();
queueOfNodes.remove();
if (currNode != null) {
queueOfNodes.add(currNode.left);
queueOfNodes.add(currNode.right);
} else {
queueOfNodes.add(null);
queueOfNodes.add(null);
}
}
level++;
}
}
public static void main(String[] args) {
PrettyPrintTree lcs = new PrettyPrintTree(Arrays.asList(80, 30, 90, 20,
100, 99, 40, 10, 25, 35, 50, 5, 15, 23, 28, 33, 38, 41, 55));
PrettyPrintTree.prettyPrintTree(lcs.root);
}
}
Solution
nodesAtHeight.toString().replaceFirst("\s+$", "")
This will recompile a regex each time it is called.
Instead you can create a constant to hold the pattern:
private static final Pattern END_OF_LINE_WHITESPACE = Pattern.compile(“s+$”);
and then use it with
END_OF_LINE_WHITESPACE.matcher(nodesAtHeight.toString()).replaceFirst("")
However just finding how many whitespaces are at the end of a string is easy enough to allow for a utility method of the form.
public static String trimEnd(String in){
for(int i = in.length(); i > 0;i--){
if(!Character.isWhitespace(in.charAt(i-1))){
return in.subString(0, i);
}
}
return "";
}
I think your code is modular but I think it is good idea to put the static functions in a separate file named Utility or something. This way you separate Tree data structure and the utility methods so they can be easily reused.
public class PrettyPrintTree {
public final TreeNode root;
public PrettyPrintTree(List<Integer> list) {
root = PrettyPrintTreeUtil.createTree(list);
}
}
class TreeNode {
TreeNode left;
TreeNode right;
int value;
public TreeNode(int value) {
this.value = value;
}
}
class PrettyPrintTreeUtil{
//all the static utility methods...
}