How to print binary tree diagram in Java?
I've created simple binary tree printer. You can use and modify it as you want, but it's not optimized anyway. I think that a lot of things can be improved here ;)
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BTreePrinterTest {
private static Node<Integer> test1() {
Node<Integer> root = new Node<Integer>(2);
Node<Integer> n11 = new Node<Integer>(7);
Node<Integer> n12 = new Node<Integer>(5);
Node<Integer> n21 = new Node<Integer>(2);
Node<Integer> n22 = new Node<Integer>(6);
Node<Integer> n23 = new Node<Integer>(3);
Node<Integer> n24 = new Node<Integer>(6);
Node<Integer> n31 = new Node<Integer>(5);
Node<Integer> n32 = new Node<Integer>(8);
Node<Integer> n33 = new Node<Integer>(4);
Node<Integer> n34 = new Node<Integer>(5);
Node<Integer> n35 = new Node<Integer>(8);
Node<Integer> n36 = new Node<Integer>(4);
Node<Integer> n37 = new Node<Integer>(5);
Node<Integer> n38 = new Node<Integer>(8);
root.left = n11;
root.right = n12;
n11.left = n21;
n11.right = n22;
n12.left = n23;
n12.right = n24;
n21.left = n31;
n21.right = n32;
n22.left = n33;
n22.right = n34;
n23.left = n35;
n23.right = n36;
n24.left = n37;
n24.right = n38;
return root;
}
private static Node<Integer> test2() {
Node<Integer> root = new Node<Integer>(2);
Node<Integer> n11 = new Node<Integer>(7);
Node<Integer> n12 = new Node<Integer>(5);
Node<Integer> n21 = new Node<Integer>(2);
Node<Integer> n22 = new Node<Integer>(6);
Node<Integer> n23 = new Node<Integer>(9);
Node<Integer> n31 = new Node<Integer>(5);
Node<Integer> n32 = new Node<Integer>(8);
Node<Integer> n33 = new Node<Integer>(4);
root.left = n11;
root.right = n12;
n11.left = n21;
n11.right = n22;
n12.right = n23;
n22.left = n31;
n22.right = n32;
n23.left = n33;
return root;
}
public static void main(String[] args) {
BTreePrinter.printNode(test1());
BTreePrinter.printNode(test2());
}
}
class Node<T extends Comparable<?>> {
Node<T> left, right;
T data;
public Node(T data) {
this.data = data;
}
}
class BTreePrinter {
public static <T extends Comparable<?>> void printNode(Node<T> root) {
int maxLevel = BTreePrinter.maxLevel(root);
printNodeInternal(Collections.singletonList(root), 1, maxLevel);
}
private static <T extends Comparable<?>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) {
if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
return;
int floor = maxLevel - level;
int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
int firstSpaces = (int) Math.pow(2, (floor)) - 1;
int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;
BTreePrinter.printWhitespaces(firstSpaces);
List<Node<T>> newNodes = new ArrayList<Node<T>>();
for (Node<T> node : nodes) {
if (node != null) {
System.out.print(node.data);
newNodes.add(node.left);
newNodes.add(node.right);
} else {
newNodes.add(null);
newNodes.add(null);
System.out.print(" ");
}
BTreePrinter.printWhitespaces(betweenSpaces);
}
System.out.println("");
for (int i = 1; i <= endgeLines; i++) {
for (int j = 0; j < nodes.size(); j++) {
BTreePrinter.printWhitespaces(firstSpaces - i);
if (nodes.get(j) == null) {
BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
continue;
}
if (nodes.get(j).left != null)
System.out.print("/");
else
BTreePrinter.printWhitespaces(1);
BTreePrinter.printWhitespaces(i + i - 1);
if (nodes.get(j).right != null)
System.out.print("\\");
else
BTreePrinter.printWhitespaces(1);
BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
}
System.out.println("");
}
printNodeInternal(newNodes, level + 1, maxLevel);
}
private static void printWhitespaces(int count) {
for (int i = 0; i < count; i++)
System.out.print(" ");
}
private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
if (node == null)
return 0;
return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
}
private static <T> boolean isAllElementsNull(List<T> list) {
for (Object object : list) {
if (object != null)
return false;
}
return true;
}
}
Output 1 :
2
/ \
/ \
/ \
/ \
7 5
/ \ / \
/ \ / \
2 6 3 6
/ \ / \ / \ / \
5 8 4 5 8 4 5 8
Output 2 :
2
/ \
/ \
/ \
/ \
7 5
/ \ \
/ \ \
2 6 9
/ \ /
5 8 4
How to print binary search tree in nice diagram?
You could use these functions. They return a string, so it is up to the caller to print it.
I also find it nicer when the right subtree is printed upwards, and the left subtree downwards. That way, the tree is just rotated 90° from how it is usually depicted -- with the root at the top.
Here is the relevant code:
public String pretty() {
return pretty(root, "", 1);
}
private String pretty(Node root, String prefix, int dir) {
if (root == null) {
return "";
}
String space = " ".repeat(("" + root.data).length());
return pretty(root.right, prefix + "│ ".charAt(dir) + space, 2)
+ prefix + "└ ┌".charAt(dir) + root.data
+ " ┘┐┤".charAt((root.left != null ? 2 : 0)
+ (root.right != null ? 1 : 0)) + "\n"
+ pretty(root.left, prefix + " │".charAt(dir) + space, 0);
}
Printing values in a tree structure in Java?
This approach runs into trouble because any calls to println() preclude printing further nodes on a line. Using a level order traversal/BFS will enable you to call println() to move to the next line only when all nodes on a given tree level have already been printed.
The bigger difficulty lies in keeping track of the horizontal placement of each node in a level. Doing this properly involves considering the depth, length of the node data and any empty children. If you can, consider printing your tree with depth increasing from left to right, similar to the unix command tree, rather than top-down, which simplifies the algorithm.
Here's a proof-of-concept for a top-down print. Spacing formulas are from this excellent post on this very topic. The strategy I used is to run a BFS using a queue, storing nodes (and null placeholders) in a list per level. Once the end of a level is reached, spacing is determined based on the number of nodes on a level, which is 2n-1, and printed. A simplifying assumption is that node data width is 1.
import java.util.*;
import static java.lang.System.out;
public class Main {
static void printLevelOrder(Node root) {
LinkedList<QItem> queue = new LinkedList<>();
ArrayList<Node> level = new ArrayList<>();
int depth = height(root);
queue.add(new QItem(root, depth));
for (;;) {
QItem curr = queue.poll();
if (curr.depth < depth) {
depth = curr.depth;
for (int i = (int)Math.pow(2, depth) - 1; i > 0; i--) {
out.print(" ");
}
for (Node n : level) {
out.print(n == null ? " " : n.val);
for (int i = (int)Math.pow(2, depth + 1); i > 1; i--) {
out.print(" ");
}
}
out.println();
level.clear();
if (curr.depth <= 0) {
break;
}
}
level.add(curr.node);
if (curr.node == null) {
queue.add(new QItem(null, depth - 1));
queue.add(new QItem(null, depth - 1));
}
else {
queue.add(new QItem(curr.node.left, depth - 1));
queue.add(new QItem(curr.node.right, depth - 1));
}
}
}
static int height(Node root) {
return root == null ? 0 : 1 + Math.max(
height(root.left), height(root.right)
);
}
public static void main(String[] args) {
printLevelOrder(
new Node<Integer>(
1,
new Node<Integer>(
2,
new Node<Integer>(
4,
new Node<Integer>(7, null, null),
new Node<Integer>(8, null, null)
),
null
),
new Node<Integer>(
3,
new Node<Integer>(
5,
new Node<Integer>(9, null, null),
null
),
new Node<Integer>(
6,
null,
new Node<Character>('a', null, null)
)
)
)
);
}
}
class Node<T> {
Node left;
Node right;
T val;
public Node(T val, Node left, Node right) {
this.left = left;
this.right = right;
this.val = val;
}
}
class QItem {
Node node;
int depth;
public QItem(Node node, int depth) {
this.node = node;
this.depth = depth;
}
}
Output:
1
2 3
4 5 6
7 8 9 a
Try it!
How to solve problem with binary tree print
Thank you for posting the rest of the code. Your issue is with the PrintableTree interface in method getInstance. You return a new TreeNode (it comes initialized with 0 as int is a primitive type and cannot be null). And then you add the rest of the nodes to that original node with 0. You most likely wanted to return a new BinaryTree instead. However you need to change your code as BinaryTree does not implement the PrintableTree interface.
Here are the changes necessary to fix it:
In PrintableTree.java
static PrintableTree getInstance() {
return new BinaryTree();
}
In BinaryTree.java
// notice the added implements
class BinaryTree implements PrintableTree {
// the rest of the class is fine, add this to the end
@Override
public String prettyPrint() {
if (root != null) {
return root.prettyPrint();
}
return "";
}
}
Also the class TreeNode does not need to extend BinaryTree as a node is not a tree (it doesn't make sense for the node the contain a value AND a root). If your assignment requires this relation then edit the code accordingly.
Print Binary Tree By Tilting Your Head
Try printing the right node before you print the indentations for the current node. Something like this:
private void showTree(TNode myRoot,int myLevel)
{
if(myRoot == null)
{
return;
}
showTree(myRoot.right, myLevel + 1);
for(int i = 0; i < myLevel; i++)
{
System.out.print("\t");
}
System.out.println(myRoot.data.toStr());
showTree(myRoot.left, myLevel + 1);
}
Also I think you should start at level 0, call showTree(_root,0);
I personally think it would be more readable if you would combine the indentation to one string and then print it. something like this:
private void showTree(TNode myRoot,int myLevel)
{
if(myRoot == null)
{
return;
}
String currentNodeIdentation = "";
for(int i = 0; i < myLevel; i++)
{
currentNodeIdentation += "\t";
}
showTree(myRoot.right, myLevel + 1);
System.out.println(currentNodeIdentation + myRoot.data.toStr());
showTree(myRoot.left, myLevel + 1);
}
Or if you have java 11 you can even use currentNodeIdentation = "\t".repeat(myLevel).
How to print A binary tree?
I recommend you implement a toString, rather than this TreePrinter.
I've slightly changed your Node class, moved it outside the SortTree, resulting in the code available from https://github.com/johanwitters/stackoverflow-tree-printer.
The implementation of Node is here:
package com.johanw.stackoverflow.tree;
import com.johanw.stackoverflow.util.Helper;
public class Node<A extends Comparable>{
private static int AMOUNT_INDENT = 3;
private int data;
private Node left, right;
public Node(int d) {
data = d;
left = null;
right = null;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
public int getData() {
return data;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
public void indent(StringBuilder builder, int indent) {
builder.append(Helper.repeat(indent * (AMOUNT_INDENT + 1), " "));
}
public void newLine(StringBuilder builder) {
builder.append(System.lineSeparator());
}
public String toString(int indent) {
StringBuilder builder = new StringBuilder();
builder.append(data);
newLine(builder);
if (left != null) {
indent(builder, indent);
builder.append("└" + Helper.repeat(AMOUNT_INDENT, "─") + left.toString(indent + 1));
}
if (right != null) {
indent(builder, indent);
builder.append("└" + Helper.repeat(AMOUNT_INDENT, "─") + right.toString(indent + 1));
}
return builder.toString();
}
@Override
public String toString() {
return toString(0);
}
}
The below unit test gives the bottom output for the given tree structure:
public class TestSortTree {
@Test
public void test() {
Node node = new Node(1);
Node left = new Node(2);
Node leftLeft = new Node(22);
Node leftRight = new Node(23);
Node leftRightLeft = new Node(24);
left.setLeft(leftLeft);
leftRight.setLeft(new Node(39));
left.setRight(leftRight);
node.setLeft(left);
node.setRight(new Node(3));
System.out.println(node.toString());
}
}
I hope this helps
How to print BinaryTree in Java?
Got the solution for those who need it:
private String spaces(int count){
String spaces="";
while(count>0){
spaces=spaces+" ";
count=count-1;
}
return spaces;
}
private String toString(int depth){
String str="";
if(left!=null)
{
str=str+left.toString(depth+1);
}
str=str+spaces(depth)+data.toString()+"\n";
if(right!=null)
{
str=str+right.toString(depth+1);
}
return str;
}
private String toString(String str){
if(left!=null)
str=str+left.toString(" ");
str=str+data.toString()+"\n";
if(right!=null)
str=str+right.toString(" ");
return str;
}
Related Topics
What's the Difference Between Concurrenthashmap and Collections.Synchronizedmap(Map)
Compiling a Java Program into an Executable
How to See Jit-Compiled Code in Jvm
Java Io Implementation of Unix/Linux "Tail -F"
Java, Classpath, Classloading => Multiple Versions of the Same Jar/Project
Javafx Fxml Controller - Constructor VS Initialize Method
Jtable Not Showing Up on Jframe (Java)
Sorting a Collection of Objects
How to Wire One Pane to Another
Display Indeterminate Jprogressbar While Batch File Runs
Jformattedtextfield Is Not Properly Cleared
Can You Recommend a Java Library for Reading (And Possibly Writing) CSV Files
Centering a Jlabel on a JPAnel