How can I print a binary tree in Java so that the output is like:
4
/ \
2 5
My node:
public class Node<A extends Comparable> {
Node<A> left, right;
A data;
public Node(A data){
this.data = data;
}
}
This question is related to
java
data-structures
printing
binary-tree
The answer is
michal.kreuzman nice one I will have to say. It was useful.
However, the above works only for single digits: if you are going to use more than one digit, the structure is going to get misplaced since you are using spaces and not tabs.
As for my later codes I needed more digits than only 2, so I made a program myself.
It has some bugs now, again right now I am feeling lazy to correct them but it prints very beautifully and the nodes can take a larger number of digits.
The tree is not going to be as the question mentions but it is 270 degrees rotated :)
public static void printBinaryTree(TreeNode root, int level){
if(root==null)
return;
printBinaryTree(root.right, level+1);
if(level!=0){
for(int i=0;i<level-1;i++)
System.out.print("|\t");
System.out.println("|-------"+root.val);
}
else
System.out.println(root.val);
printBinaryTree(root.left, level+1);
}
Place this function with your own specified TreeNode and keep the level initially 0, and enjoy!
Here are some of the sample outputs:
| | |-------11
| |-------10
| | |-------9
|-------8
| | |-------7
| |-------6
| | |-------5
4
| |-------3
|-------2
| |-------1
| | | |-------10
| | |-------9
| |-------8
| | |-------7
|-------6
| |-------5
4
| |-------3
|-------2
| |-------1
Only problem is with the extending branches; I will try to solve the problem as soon as possible but till then you can use it too.
I've made an improved algorithm for this, which handles nicely nodes with different size. It prints top-down using lines.
package alg;
import java.util.ArrayList;
import java.util.List;
/**
* Binary tree printer
*
* @author MightyPork
*/
public class TreePrinter
{
/** Node that can be printed */
public interface PrintableNode
{
/** Get left child */
PrintableNode getLeft();
/** Get right child */
PrintableNode getRight();
/** Get text to be printed */
String getText();
}
/**
* Print a tree
*
* @param root
* tree root node
*/
public static void print(PrintableNode root)
{
List<List<String>> lines = new ArrayList<List<String>>();
List<PrintableNode> level = new ArrayList<PrintableNode>();
List<PrintableNode> next = new ArrayList<PrintableNode>();
level.add(root);
int nn = 1;
int widest = 0;
while (nn != 0) {
List<String> line = new ArrayList<String>();
nn = 0;
for (PrintableNode n : level) {
if (n == null) {
line.add(null);
next.add(null);
next.add(null);
} else {
String aa = n.getText();
line.add(aa);
if (aa.length() > widest) widest = aa.length();
next.add(n.getLeft());
next.add(n.getRight());
if (n.getLeft() != null) nn++;
if (n.getRight() != null) nn++;
}
}
if (widest % 2 == 1) widest++;
lines.add(line);
List<PrintableNode> tmp = level;
level = next;
next = tmp;
next.clear();
}
int perpiece = lines.get(lines.size() - 1).size() * (widest + 4);
for (int i = 0; i < lines.size(); i++) {
List<String> line = lines.get(i);
int hpw = (int) Math.floor(perpiece / 2f) - 1;
if (i > 0) {
for (int j = 0; j < line.size(); j++) {
// split node
char c = ' ';
if (j % 2 == 1) {
if (line.get(j - 1) != null) {
c = (line.get(j) != null) ? '-' : '+';
} else {
if (j < line.size() && line.get(j) != null) c = '+';
}
}
System.out.print(c);
// lines and spaces
if (line.get(j) == null) {
for (int k = 0; k < perpiece - 1; k++) {
System.out.print(" ");
}
} else {
for (int k = 0; k < hpw; k++) {
System.out.print(j % 2 == 0 ? " " : "-");
}
System.out.print(j % 2 == 0 ? "+" : "+");
for (int k = 0; k < hpw; k++) {
System.out.print(j % 2 == 0 ? "-" : " ");
}
}
}
System.out.println();
}
// print line of numbers
for (int j = 0; j < line.size(); j++) {
String f = line.get(j);
if (f == null) f = "";
int gap1 = (int) Math.ceil(perpiece / 2f - f.length() / 2f);
int gap2 = (int) Math.floor(perpiece / 2f - f.length() / 2f);
// a number
for (int k = 0; k < gap1; k++) {
System.out.print(" ");
}
System.out.print(f);
for (int k = 0; k < gap2; k++) {
System.out.print(" ");
}
}
System.out.println();
perpiece /= 2;
}
}
}
To use this for your Tree, let your Node class implement PrintableNode.
Example output:
2952:0
+-----------------------------------------------+
1249:-1 5866:0
+-----------------------+ +-----------------------+
491:-1 1572:0 4786:1 6190:0
+-----+ +-----+ +-----------+
339:0 5717:0 6061:0 6271:0
You can use an applet to visualize this very easily. You need to print the following items.
Print the nodes as circles with some visible radius
Get the coordinates for each node.
The x coordinate can be visualized as the number of nodes visited before the node is visited in its inorder traversal.
The y coordinate can be visualized as the depth of the particular node.
Print the lines between parent and children
This can be done by maintaining the x and y coordinates of the nodes and the parents of each node in separate lists.
For each node except root join each node with its parent by taking the x and y coordinates of both the child and the parent.
this is one of the simplest version i could implement. i hope it helps you
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def add(self, data):
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.add(data)
if data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.add(data)
def display(self):
diff = 16
start = 50
c = ' '
this_level = [(self, start)]
while this_level:
next_level = list()
last_line = ''
for node, d in this_level:
line = last_line + c*(d - len(last_line)) + str(node.data)
print(line, end='\r')
last_line = line
if node.left:
next_level.append((node.left, d - diff))
if node.right:
next_level.append((node.right, d + diff))
this_level = next_level
diff = max(diff//2, 2)
print('\n')
if __name__ == '__main__':
from random import randint, choice
values = [randint(0, 100) for _ in range(10)]
bst = Node(choice(values))
for data in values:
bst.add(data)
bst.display()
- You will need to level order traverse your tree.
- Choose node length and space length.
- Get the tree's base width relative to each level which is
node_length * nodes_count + space_length * spaces_count*. - Find a relation between branching, spacing, indentation and the calculated base width.
Code on GitHub: YoussefRaafatNasry/bst-ascii-visualization
07
/\
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
03 11
/\ /\
/ \ / \
/ \ / \
/ \ / \
/ \ / \
01 05 09 13
/\ /\ /\ /\
/ \ / \ / \ / \
00 02 04 06 08 10 12 14
Print in Console:
500
700 300
200 400
Simple code :
public int getHeight()
{
if(rootNode == null) return -1;
return getHeight(rootNode);
}
private int getHeight(Node node)
{
if(node == null) return -1;
return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
public void printBinaryTree(Node rootNode)
{
Queue<Node> rootsQueue = new LinkedList<Node>();
Queue<Node> levelQueue = new LinkedList<Node>();
levelQueue.add(rootNode);
int treeHeight = getHeight();
int firstNodeGap;
int internalNodeGap;
int copyinternalNodeGap;
while(true)
{
System.out.println("");
internalNodeGap = (int)(Math.pow(2, treeHeight + 1) -1);
copyinternalNodeGap = internalNodeGap;
firstNodeGap = internalNodeGap/2;
boolean levelFirstNode = true;
while(!levelQueue.isEmpty())
{
internalNodeGap = copyinternalNodeGap;
Node currNode = levelQueue.poll();
if(currNode != null)
{
if(levelFirstNode)
{
while(firstNodeGap > 0)
{
System.out.format("%s", " ");
firstNodeGap--;
}
levelFirstNode =false;
}
else
{
while(internalNodeGap>0)
{
internalNodeGap--;
System.out.format("%s", " ");
}
}
System.out.format("%3d",currNode.data);
rootsQueue.add(currNode);
}
}
--treeHeight;
while(!rootsQueue.isEmpty())
{
Node currNode = rootsQueue.poll();
if(currNode != null)
{
levelQueue.add(currNode.left);
levelQueue.add(currNode.right);
}
}
if(levelQueue.isEmpty()) break;
}
}
Here is another way to visualize your tree: save the nodes as an xml file and then let your browser show you the hierarchy:
class treeNode{
int key;
treeNode left;
treeNode right;
public treeNode(int key){
this.key = key;
left = right = null;
}
public void printNode(StringBuilder output, String dir){
output.append("<node key='" + key + "' dir='" + dir + "'>");
if(left != null)
left.printNode(output, "l");
if(right != null)
right.printNode(output, "r");
output.append("</node>");
}
}
class tree{
private treeNode treeRoot;
public tree(int key){
treeRoot = new treeNode(key);
}
public void insert(int key){
insert(treeRoot, key);
}
private treeNode insert(treeNode root, int key){
if(root == null){
treeNode child = new treeNode(key);
return child;
}
if(key < root.key)
root.left = insert(root.left, key);
else if(key > root.key)
root.right = insert(root.right, key);
return root;
}
public void saveTreeAsXml(){
StringBuilder strOutput = new StringBuilder();
strOutput.append("<?xml version=\"1.0\" encoding=\"UTF-8\"?>");
treeRoot.printNode(strOutput, "root");
try {
PrintWriter writer = new PrintWriter("C:/tree.xml", "UTF-8");
writer.write(strOutput.toString());
writer.close();
}
catch (FileNotFoundException e){
}
catch(UnsupportedEncodingException e){
}
}
}
Here is code to test it:
tree t = new tree(1);
t.insert(10);
t.insert(5);
t.insert(4);
t.insert(20);
t.insert(40);
t.insert(30);
t.insert(80);
t.insert(60);
t.insert(50);
t.saveTreeAsXml();
And the output looks like this:
Your tree will need twice the distance for each layer:
a
/ \
/ \
/ \
/ \
b c
/ \ / \
/ \ / \
d e f g
/ \ / \ / \ / \
h i j k l m n o
You can save your tree in an array of arrays, one array for every depth:
[[a],[b,c],[d,e,f,g],[h,i,j,k,l,m,n,o]]
If your tree is not full, you need to include empty values in that array:
a
/ \
/ \
/ \
/ \
b c
/ \ / \
/ \ / \
d e f g
/ \ \ / \ \
h i k l m o
[[a],[b,c],[d,e,f,g],[h,i, ,k,l,m, ,o]]
Then you can iterate over the array to print your tree, printing spaces before the first element and between the elements depending on the depth and printing the lines depending on if the corresponding elements in the array for the next layer are filled or not. If your values can be more than one character long, you need to find the longest value while creating the array representation and multiply all widths and the number of lines accordingly.
using map...
{
Map<Integer,String> m = new LinkedHashMap<>();
tn.printNodeWithLvl(node,l,m);
for(Entry<Integer, String> map :m.entrySet()) {
System.out.println(map.getValue());
}
then....method
private void printNodeWithLvl(Node node,int l,Map<Integer,String> m) {
if(node==null) {
return;
}
if(m.containsKey(l)) {
m.put(l, new StringBuilder(m.get(l)).append(node.value).toString());
}else {
m.put(l, node.value+"");
}
l++;
printNodeWithLvl( node.left,l,m);
printNodeWithLvl(node.right,l,m);
}
}
I wrote a binary tree printer in Java.
Code is on GitHub here.
It hasn't been optimized for run time efficiency, but since we're talking about printing in ASCII, I figured it's not going to be used on very large trees. It does have some nice features though.
- It makes efficient use of space in that a large subtree extends under a smaller one as much as possible.
- There's a parameter to set the minimum horizontal space between node labels.
- Node labels are strings of arbitrary length.
- In addition to a method for printing a single tree, there's a method for printing a list of trees horizontally across the page (with a parameter for page width), using as many rows as necessary.
- There's an option to print trees with diagonal branches (using slash and backslash characters) or with horizontal branches (using ascii box drawing characters). The latter is more compact and makes tree levels more visually clear.
- It works.
Some demo/test programs are included.
An example of a randomly generated binary tree, as printed by the program, follows. This illustrates the efficient use of space, with a large right subtree extending under a small left subtree:
seven
/ \
/ \
/ \
/ \
/ \
/ \
five thirteen
/ \ / \
/ \ / \
/ \ / \
three six / \
/ \ / \
/ \ / \
one four / \
\ / \
two / \
nine twenty four
/ \ / \
/ \ / \
/ \ / \
eight twelve / \
/ / \
ten / \
\ / \
eleven / \
/ \
/ \
/ \
eighteen twenty seven
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ twenty five twenty eight
/ \ \ \
/ \ twenty six thirty
fourteen nineteen /
\ \ twenty nine
sixteen twenty three
/ \ /
/ \ twenty two
/ \ /
/ \ twenty
/ \ \
fifteen seventeen twenty one
An example of printing all five node binary trees (with in-order labels) across the page:
one one one one one one one
\ \ \ \ \ \ \
two two two two two three three
\ \ \ \ \ / \ / \
three three four five five two four two five
\ \ / \ / / \ /
four five / \ three four five four
\ / three five \ /
five four four three
one one one one one one one two
\ \ \ \ \ \ \ / \
four four five five five five five / \
/ \ / \ / / / / / one three
two five / \ two two three four four \
\ three five \ \ / \ / / four
three / three four two four two three \
two \ / \ / five
four three three two
two two two two three three three
/ \ / \ / \ / \ / \ / \ / \
/ \ one four one five one five one four / \ two four
one three / \ / / \ \ / \ / \
\ / \ three four two five one five one five
five three five \ / \ /
/ four three two four
four
three four four four four four five
/ \ / \ / \ / \ / \ / \ /
two five one five one five two five / \ / \ one
/ / \ \ / \ three five three five \
one four two three / \ / / two
\ / one three one two \
three two \ / three
two one \
four
five five five five five five five five
/ / / / / / / /
one one one one two two three three
\ \ \ \ / \ / \ / \ / \
two three four four / \ one four one four two four
\ / \ / / one three / \ /
four two four two three \ three two one
/ \ / four
three three two
five five five five five
/ / / / /
four four four four four
/ / / / /
one one two three three
\ \ / \ / /
two three / \ one two
\ / one three \ /
three two two one
The following is an example of the same tree printed 4 different ways, with horizontal spacing of 1 and of 3, and with diagonal and horizontal branches.
27
+-----------+
13 29
+-------------+ +---+
8 23 28 30
+-----+ +-----+
4 11 21 26
+---+ +-+ +---+ ++
2 5 9 12 18 22 24
+-+ ++ ++ +---+ ++
1 3 6 10 17 19 25
++ ++ ++
7 15 20
+---+
14 16
27
/ \
/ \
13 29
/ \ / \
/ \ 28 30
/ \
/ \
/ \
/ \
8 23
/ \ / \
/ \ / \
4 11 / \
/ \ / \ 21 26
2 5 9 12 / \ /
/ \ \ \ 18 22 24
1 3 6 10 / \ \
\ 17 19 25
7 / \
15 20
/ \
14 16
27
+-----------------+
13 29
+-------------------+ +-----+
8 23 28 30
+---------+ +---------+
4 11 21 26
+-----+ +---+ +-----+ ++
2 5 9 12 18 22 24
+---+ ++ ++ +-----+ ++
1 3 6 10 17 19 25
++ ++ ++
7 15 20
+-----+
14 16
27
/ \
/ \
/ \
/ \
13 29
/ \ / \
/ \ / \
/ \ 28 30
/ \
/ \
/ \
/ \
/ \
8 23
/ \ / \
/ \ / \
/ \ / \
4 11 / \
/ \ / \ 21 26
2 5 9 12 / \ /
/ \ \ \ / \ 24
1 3 6 10 18 22 \
\ / \ 25
7 / \
17 19
/ \
15 20
/ \
/ \
14 16
Simple python code for Leetcode style tables binary tree visualization posted here. Also cloned here
Input:
[9,5,4,5,null,2,6,2,5,null,8,3,9,2,3,1,1,null,4,5,4,2,2,6,4,null,null,1,7,null,5,4,7,null,null,7,null,1,5,6,1,null,null,null,null,9,2,null,9,7,2,1,null,null,null,6,null,null,null,null,null,null,null,null,null,5,null,null,3,null,null,null,8,null,1,null,null,8,null,null,null,null,2,null,8,7]
Output:
A Scala solution, adapted from Vasya Novikov's answer and specialized for binary trees:
/** An immutable Binary Tree. */
case class BTree[T](value: T, left: Option[BTree[T]], right: Option[BTree[T]]) {
/* Adapted from: http://stackoverflow.com/a/8948691/643684 */
def pretty: String = {
def work(tree: BTree[T], prefix: String, isTail: Boolean): String = {
val (line, bar) = if (isTail) ("+-- ", " ") else ("+-- ", "¦")
val curr = s"${prefix}${line}${tree.value}"
val rights = tree.right match {
case None => s"${prefix}${bar} +-- Ø"
case Some(r) => work(r, s"${prefix}${bar} ", false)
}
val lefts = tree.left match {
case None => s"${prefix}${bar} +-- Ø"
case Some(l) => work(l, s"${prefix}${bar} ", true)
}
s"${curr}\n${rights}\n${lefts}"
}
work(this, "", true)
}
}
I found VasyaNovikov's answer very useful for printing a large general tree, and modified it for a binary tree
Code:
class TreeNode {
Integer data = null;
TreeNode left = null;
TreeNode right = null;
TreeNode(Integer data) {this.data = data;}
public void print() {
print("", this, false);
}
public void print(String prefix, TreeNode n, boolean isLeft) {
if (n != null) {
System.out.println (prefix + (isLeft ? "|-- " : "\\-- ") + n.data);
print(prefix + (isLeft ? "| " : " "), n.left, true);
print(prefix + (isLeft ? "| " : " "), n.right, false);
}
}
}
Sample output:
\-- 7
|-- 3
| |-- 1
| | \-- 2
| \-- 5
| |-- 4
| \-- 6
\-- 11
|-- 9
| |-- 8
| \-- 10
\-- 13
|-- 12
\-- 14
public void printPreety() {
List<TreeNode> list = new ArrayList<TreeNode>();
list.add(head);
printTree(list, getHeight(head));
}
public int getHeight(TreeNode head) {
if (head == null) {
return 0;
} else {
return 1 + Math.max(getHeight(head.left), getHeight(head.right));
}
}
/**
* pass head node in list and height of the tree
*
* @param levelNodes
* @param level
*/
private void printTree(List<TreeNode> levelNodes, int level) {
List<TreeNode> nodes = new ArrayList<TreeNode>();
//indentation for first node in given level
printIndentForLevel(level);
for (TreeNode treeNode : levelNodes) {
//print node data
System.out.print(treeNode == null?" ":treeNode.data);
//spacing between nodes
printSpacingBetweenNodes(level);
//if its not a leaf node
if(level>1){
nodes.add(treeNode == null? null:treeNode.left);
nodes.add(treeNode == null? null:treeNode.right);
}
}
System.out.println();
if(level>1){
printTree(nodes, level-1);
}
}
private void printIndentForLevel(int level){
for (int i = (int) (Math.pow(2,level-1)); i >0; i--) {
System.out.print(" ");
}
}
private void printSpacingBetweenNodes(int level){
//spacing between nodes
for (int i = (int) ((Math.pow(2,level-1))*2)-1; i >0; i--) {
System.out.print(" ");
}
}
Prints Tree in following format:
4
3 7
1 5 8
2 10
9
Adapted from Vasya Novikov's answer to make it more binary, and use a StringBuilder for efficiency (concatenating String objects together in Java is generally inefficient).
public StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) {
if(right!=null) {
right.toString(new StringBuilder().append(prefix).append(isTail ? "¦ " : " "), false, sb);
}
sb.append(prefix).append(isTail ? "+-- " : "+-- ").append(value.toString()).append("\n");
if(left!=null) {
left.toString(new StringBuilder().append(prefix).append(isTail ? " " : "¦ "), true, sb);
}
return sb;
}
@Override
public String toString() {
return this.toString(new StringBuilder(), true, new StringBuilder()).toString();
}
Output:
¦ +-- 7
¦ +-- 6
¦ ¦ +-- 5
+-- 4
¦ +-- 3
+-- 2
+-- 1
+-- 0
This is a very simple solution to print out a tree. It is not that pretty, but it is really simple:
enum { kWidth = 6 };
void PrintSpace(int n)
{
for (int i = 0; i < n; ++i)
printf(" ");
}
void PrintTree(struct Node * root, int level)
{
if (!root) return;
PrintTree(root->right, level + 1);
PrintSpace(level * kWidth);
printf("%d", root->data);
PrintTree(root->left, level + 1);
}
Sample output:
106
105
104
103
102
101
100
This was the simplest solution for horizontal view. Tried with bunch of examples. Works well for my purpose. Updated from @nitin-k 's answer.
public void print(String prefix, BTNode n, boolean isLeft) {
if (n != null) {
print(prefix + " ", n.right, false);
System.out.println (prefix + ("|-- ") + n.data);
print(prefix + " ", n.left, true);
}
}
Call:
bst.print("", bst.root, false);
Solution:
|-- 80
|-- 70
|-- 60
|-- 50
|-- 40
|-- 30
|-- 20
|-- 10
Print a [large] tree by lines.
output example:
z
+-- c
¦ +-- a
¦ +-- b
+-- d
+-- e
¦ +-- asdf
+-- f
code:
public class TreeNode {
final String name;
final List<TreeNode> children;
public TreeNode(String name, List<TreeNode> children) {
this.name = name;
this.children = children;
}
public String toString() {
StringBuilder buffer = new StringBuilder(50);
print(buffer, "", "");
return buffer.toString();
}
private void print(StringBuilder buffer, String prefix, String childrenPrefix) {
buffer.append(prefix);
buffer.append(name);
buffer.append('\n');
for (Iterator<TreeNode> it = children.iterator(); it.hasNext();) {
TreeNode next = it.next();
if (it.hasNext()) {
next.print(buffer, childrenPrefix + "+-- ", childrenPrefix + "¦ ");
} else {
next.print(buffer, childrenPrefix + "+-- ", childrenPrefix + " ");
}
}
}
}
P.S. This answer doesn't exactly focus on "binary" trees -- instead, it prints all kinds of trees. Solution is inspired by the "tree" command in linux.
I know you guys all have great solution; I just want to share mine - maybe that is not the best way, but it is perfect for myself!
With python and pip on, it is really quite simple! BOOM!
On Mac or Ubuntu (mine is mac)
- open terminal
$ pip install drawtree$python, enter python console; you can do it in other wayfrom drawtree import draw_level_orderdraw_level_order('{2,1,3,0,7,9,1,2,#,1,0,#,#,8,8,#,#,#,#,7}')
DONE!
2
/ \
/ \
/ \
1 3
/ \ / \
0 7 9 1
/ / \ / \
2 1 0 8 8
/
7
Source tracking:
Before I saw this post, I went google "binary tree plain text"
And I found this https://www.reddit.com/r/learnpython/comments/3naiq8/draw_binary_tree_in_plain_text/, direct me to this https://github.com/msbanik/drawtree
public static class Node<T extends Comparable<T>> {
T value;
Node<T> left, right;
public void insertToTree(T v) {
if (value == null) {
value = v;
return;
}
if (v.compareTo(value) < 0) {
if (left == null) {
left = new Node<T>();
}
left.insertToTree(v);
} else {
if (right == null) {
right = new Node<T>();
}
right.insertToTree(v);
}
}
public void printTree(OutputStreamWriter out) throws IOException {
if (right != null) {
right.printTree(out, true, "");
}
printNodeValue(out);
if (left != null) {
left.printTree(out, false, "");
}
}
private void printNodeValue(OutputStreamWriter out) throws IOException {
if (value == null) {
out.write("<null>");
} else {
out.write(value.toString());
}
out.write('\n');
}
// use string and not stringbuffer on purpose as we need to change the indent at each recursion
private void printTree(OutputStreamWriter out, boolean isRight, String indent) throws IOException {
if (right != null) {
right.printTree(out, true, indent + (isRight ? " " : " | "));
}
out.write(indent);
if (isRight) {
out.write(" /");
} else {
out.write(" \\");
}
out.write("----- ");
printNodeValue(out);
if (left != null) {
left.printTree(out, false, indent + (isRight ? " | " : " "));
}
}
}
will print:
/----- 20
| \----- 15
/----- 14
| \----- 13
/----- 12
| | /----- 11
| \----- 10
| \----- 9
8
| /----- 7
| /----- 6
| | \----- 5
\----- 4
| /----- 3
\----- 2
\----- 1
for the input
8 4 12 2 6 10 14 1 3 5 7 9 11 13 20 15
this is a variant from @anurag's answer - it was bugging me to see the extra |s
I needed to print a binary tree in one of my projects, for that I have prepared a java class TreePrinter, one of the sample output is:
[+]
/ \
/ \
/ \
/ \
/ \
[*] \
/ \ [-]
[speed] [2] / \
[45] [12]
Here is the code for class TreePrinter along with class TextNode. For printing any tree you can just create an equivalent tree with TextNode class.
import java.util.ArrayList;
public class TreePrinter {
public TreePrinter(){
}
public static String TreeString(TextNode root){
ArrayList layers = new ArrayList();
ArrayList bottom = new ArrayList();
FillBottom(bottom, root); DrawEdges(root);
int height = GetHeight(root);
for(int i = 0; i s.length()) min = s.length();
if(!n.isEdge) s += "[";
s += n.text;
if(!n.isEdge) s += "]";
layers.set(n.depth, s);
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i temp = new ArrayList();
for(int i = 0; i 0) temp.get(i-1).left = x;
temp.add(x);
}
temp.get(count-1).left = n.left;
n.left.depth = temp.get(count-1).depth+1;
n.left = temp.get(0);
DrawEdges(temp.get(count-1).left);
}
if(n.right != null){
int count = n.right.x - (n.x + n.text.length() + 2);
ArrayList temp = new ArrayList();
for(int i = 0; i 0) temp.get(i-1).right = x;
temp.add(x);
}
temp.get(count-1).right = n.right;
n.right.depth = temp.get(count-1).depth+1;
n.right = temp.get(0);
DrawEdges(temp.get(count-1).right);
}
}
private static void FillBottom(ArrayList bottom, TextNode n){
if(n == null) return;
FillBottom(bottom, n.left);
if(!bottom.isEmpty()){
int i = bottom.size()-1;
while(bottom.get(i).isEdge) i--;
TextNode last = bottom.get(i);
if(!n.isEdge) n.x = last.x + last.text.length() + 3;
}
bottom.add(n);
FillBottom(bottom, n.right);
}
private static boolean isLeaf(TextNode n){
return (n.left == null && n.right == null);
}
private static int GetHeight(TextNode n){
if(n == null) return 0;
int l = GetHeight(n.left);
int r = GetHeight(n.right);
return Math.max(l, r) + 1;
}
}
class TextNode {
public String text;
public TextNode parent, left, right;
public boolean isEdge;
public int x, depth;
public TextNode(String text){
this.text = text;
parent = null; left = null; right = null;
isEdge = false;
x = 0; depth = 0;
}
}
Finally here is a test class for printing given sample:
public class Test {
public static void main(String[] args){
TextNode root = new TextNode("+");
root.left = new TextNode("*"); root.left.parent = root;
root.right = new TextNode("-"); root.right.parent = root;
root.left.left = new TextNode("speed"); root.left.left.parent = root.left;
root.left.right = new TextNode("2"); root.left.right.parent = root.left;
root.right.left = new TextNode("45"); root.right.left.parent = root.right;
root.right.right = new TextNode("12"); root.right.right.parent = root.right;
System.out.println(TreePrinter.TreeString(root));
}
}
For those who looking for Rust solution:
pub struct Node {
pub value: i32,
left: Option<Box<Node>>,
right: Option<Box<Node>>
}
impl Node {
pub fn new(val: i32) -> Node {
Node {
value: val,
left: None,
right: None
}
}
pub fn getLeftNode(&self) -> Option<&Node> {
self.left.as_deref()
}
pub fn getRightNode(&self) -> Option<&Node> {
self.right.as_deref()
}
pub fn setLeftNode(&mut self, val: i32) -> &mut Node {
self.left = Some(Box::new(Node::new(val)));
self.left.as_deref_mut().unwrap()
}
pub fn setRightNode(&mut self, val: i32) -> &mut Node {
self.right = Some(Box::new(Node::new(val)));
self.right.as_deref_mut().unwrap()
}
fn visualizeTree(&self, level: u16, is_tail: bool, columns: &mut HashSet<u16>) {
let left = self.getLeftNode();
let right = self.getRightNode();
if right.is_some() {
right.unwrap().visualizeTree(level+1, false, columns);
}
if level > 0 {
for i in 0..level-1 {
if columns.contains(&i) {
print!("¦ ");
} else {
print!(" ");
}
}
if is_tail {
println!("+-- {}", self.value);
columns.remove(&(level-1));
columns.insert(level);
} else {
println!("+-- {}", self.value);
columns.insert(level);
columns.insert(level-1);
}
} else {
println!("{}", self.value);
}
if left.is_some() {
left.unwrap().visualizeTree(level+1, true, columns);
}
}
pub fn printTree(&self) {
let mut columns = HashSet::new();
columns.insert(0);
self.visualizeTree(0, true, &mut columns);
}
}
The output is something like this:
+-- 17
¦ ¦ +-- 3
¦ ¦ ¦ +-- 9
¦ +-- 2
¦ +-- 1
20
¦ +-- 7
¦ ¦ ¦ +-- 16
¦ ¦ +-- 15
+-- 8
¦ +-- 11
+-- 4
+-- 13
A solution in Scala language, analogous to what I wrote in java:
case class Node(name: String, children: Node*) {
def toTree: String = toTree("", "").mkString("\n")
private def toTree(prefix: String, childrenPrefix: String): Seq[String] = {
val firstLine = prefix + this.name
val firstChildren = this.children.dropRight(1).flatMap { child =>
child.toTree(childrenPrefix + "+-- ", childrenPrefix + "¦ ")
}
val lastChild = this.children.takeRight(1).flatMap { child =>
child.toTree(childrenPrefix + "+-- ", childrenPrefix + " ")
}
firstLine +: firstChildren ++: lastChild
}
}
Output example:
vasya
+-- frosya
¦ +-- petya
¦ ¦ +-- masha
¦ +-- kolya
+-- frosya2
See also these answers.
In particular it wasn't too difficult to use abego TreeLayout to produce results shown below with the default settings.
If you try that tool, note this caveat: It prints children in the order they were added. For a BST where left vs right matters I found this library to be inappropriate without modification.
Also, the method to add children simply takes a parent and child node as parameters. (So to process a bunch of nodes, you must take the first one separately to create a root.)
I ended up using this solution above, modifying it to take in the type <Node> so as to have access to Node's left and right (children).
Based on VasyaNovikov answer. Improved with some Java magic: Generics and Functional interface.
/**
* Print a tree structure in a pretty ASCII fromat.
* @param prefix Currnet previx. Use "" in initial call!
* @param node The current node. Pass the root node of your tree in initial call.
* @param getChildrenFunc A {@link Function} that returns the children of a given node.
* @param isTail Is node the last of its sibblings. Use true in initial call. (This is needed for pretty printing.)
* @param <T> The type of your nodes. Anything that has a toString can be used.
*/
private <T> void printTreeRec(String prefix, T node, Function<T, List<T>> getChildrenFunc, boolean isTail) {
String nodeName = node.toString();
String nodeConnection = isTail ? "+-- " : "+-- ";
log.debug(prefix + nodeConnection + nodeName);
List<T> children = getChildrenFunc.apply(node);
for (int i = 0; i < children.size(); i++) {
String newPrefix = prefix + (isTail ? " " : "¦ ");
printTreeRec(newPrefix, children.get(i), getChildrenFunc, i == children.size()-1);
}
}
Example initial call:
Function<ChecksumModel, List<ChecksumModel>> getChildrenFunc = node -> getChildrenOf(node)
printTreeRec("", rootNode, getChildrenFunc, true);
Will output something like
+-- rootNode
+-- childNode1
+-- childNode2
¦ +-- childNode2.1
¦ +-- childNode2.2
¦ +-- childNode2.3
+-- childNode3
+-- childNode4
private StringBuilder prettyPrint(Node root, int currentHeight, int totalHeight) {
StringBuilder sb = new StringBuilder();
int spaces = getSpaceCount(totalHeight-currentHeight + 1);
if(root == null) {
//create a 'spatial' block and return it
String row = String.format("%"+(2*spaces+1)+"s%n", "");
//now repeat this row space+1 times
String block = new String(new char[spaces+1]).replace("\0", row);
return new StringBuilder(block);
}
if(currentHeight==totalHeight) return new StringBuilder(root.data+"");
int slashes = getSlashCount(totalHeight-currentHeight +1);
sb.append(String.format("%"+(spaces+1)+"s%"+spaces+"s", root.data+"", ""));
sb.append("\n");
//now print / and \
// but make sure that left and right exists
char leftSlash = root.left == null? ' ':'/';
char rightSlash = root.right==null? ' ':'\\';
int spaceInBetween = 1;
for(int i=0, space = spaces-1; i<slashes; i++, space --, spaceInBetween+=2) {
for(int j=0; j<space; j++) sb.append(" ");
sb.append(leftSlash);
for(int j=0; j<spaceInBetween; j++) sb.append(" ");
sb.append(rightSlash+"");
for(int j=0; j<space; j++) sb.append(" ");
sb.append("\n");
}
//sb.append("\n");
//now get string representations of left and right subtrees
StringBuilder leftTree = prettyPrint(root.left, currentHeight+1, totalHeight);
StringBuilder rightTree = prettyPrint(root.right, currentHeight+1, totalHeight);
// now line by line print the trees side by side
Scanner leftScanner = new Scanner(leftTree.toString());
Scanner rightScanner = new Scanner(rightTree.toString());
// spaceInBetween+=1;
while(leftScanner.hasNextLine()) {
if(currentHeight==totalHeight-1) {
sb.append(String.format("%-2s %2s", leftScanner.nextLine(), rightScanner.nextLine()));
sb.append("\n");
spaceInBetween-=2;
}
else {
sb.append(leftScanner.nextLine());
sb.append(" ");
sb.append(rightScanner.nextLine()+"\n");
}
}
return sb;
}
private int getSpaceCount(int height) {
return (int) (3*Math.pow(2, height-2)-1);
}
private int getSlashCount(int height) {
if(height <= 3) return height -1;
return (int) (3*Math.pow(2, height-3)-1);
}
https://github.com/murtraja/java-binary-tree-printer
only works for 1 to 2 digit integers (i was lazy to make it generic)
This is an interesting question, and I also wrote a project for it.
Here are some examples:
Print random BST.
BTPrinter.printRandomBST(100, 100);
38
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
28 82
/ \ / \
/ \ / \
/ \ / \
/ \ / \
5 31 / \
/ \ / \ / \
/ \ 30 36 / \
/ \ / / \ / \
/ \ 29 33 37 / \
/ \ / \ / \
/ \ 32 35 65 95
1 14 / / \ / \
/ \ / \ 34 / \ 94 97
0 2 / \ / \ / / \
\ 12 24 / \ 93 96 98
3 / \ / \ / \ / \
\ 9 13 16 25 / \ 84 99
4 / \ / \ \ / \ / \
7 10 15 23 26 59 74 83 86
/ \ \ / \ / \ / \ / \
6 8 11 22 27 56 60 73 76 85 91
/ / \ \ / / \ / \
20 / \ 61 67 75 79 88 92
/ \ 40 58 \ / \ / \ / \
18 21 / \ / 62 66 72 78 80 87 89
/ \ 39 54 57 \ / / \ \
17 19 / \ 64 69 77 81 90
50 55 / / \
/ \ 63 68 70
/ \ \
/ \ 71
47 53
/ \ /
/ \ 52
42 49 /
/ \ / 51
41 43 48
\
46
/
45
/
44
Print tree from leetcode-style level order array, '#' means a path terminator where no node exists below.
BTPrinter.printTree("1,2,3,4,5,#,#,6,7,8,1,#,#,#,#,#,#,2,3,4,5,6,7,8,9,10,11,12,13,14,15");
1
/ \
2 3
/ \
/ \
4 5
/ \ / \
6 7 8 1
/ \
/ \
/ \
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
Here's a very versatile tree printer. Not the best looking, but it handles a lot of cases. Feel free to add slashes if you can figure that out.
package com.tomac120.NodePrinter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* Created by elijah on 6/28/16.
*/
public class NodePrinter{
final private List<List<PrintableNodePosition>> nodesByRow;
int maxColumnsLeft = 0;
int maxColumnsRight = 0;
int maxTitleLength = 0;
String sep = " ";
int depth = 0;
public NodePrinter(PrintableNode rootNode, int chars_per_node){
this.setDepth(rootNode,1);
nodesByRow = new ArrayList<>(depth);
this.addNode(rootNode._getPrintableNodeInfo(),0,0);
for (int i = 0;i<chars_per_node;i++){
//sep += " ";
}
}
private void setDepth(PrintableNode info, int depth){
if (depth > this.depth){
this.depth = depth;
}
if (info._getLeftChild() != null){
this.setDepth(info._getLeftChild(),depth+1);
}
if (info._getRightChild() != null){
this.setDepth(info._getRightChild(),depth+1);
}
}
private void addNode(PrintableNodeInfo node, int level, int position){
if (position < 0 && -position > maxColumnsLeft){
maxColumnsLeft = -position;
}
if (position > 0 && position > maxColumnsRight){
maxColumnsRight = position;
}
if (node.getTitleLength() > maxTitleLength){
maxTitleLength = node.getTitleLength();
}
List<PrintableNodePosition> row = this.getRow(level);
row.add(new PrintableNodePosition(node, level, position));
level++;
int depthToUse = Math.min(depth,6);
int levelToUse = Math.min(level,6);
int offset = depthToUse - levelToUse-1;
offset = (int)(Math.pow(offset,Math.log(depthToUse)*1.4));
offset = Math.max(offset,3);
PrintableNodeInfo leftChild = node.getLeftChildInfo();
PrintableNodeInfo rightChild = node.getRightChildInfo();
if (leftChild != null){
this.addNode(leftChild,level,position-offset);
}
if (rightChild != null){
this.addNode(rightChild,level,position+offset);
}
}
private List<PrintableNodePosition> getRow(int row){
if (row > nodesByRow.size() - 1){
nodesByRow.add(new LinkedList<>());
}
return nodesByRow.get(row);
}
public void print(){
int max_chars = this.maxColumnsLeft+maxColumnsRight+1;
int level = 0;
String node_format = "%-"+this.maxTitleLength+"s";
for (List<PrintableNodePosition> pos_arr : this.nodesByRow){
String[] chars = this.getCharactersArray(pos_arr,max_chars);
String line = "";
int empty_chars = 0;
for (int i=0;i<chars.length+1;i++){
String value_i = i < chars.length ? chars[i]:null;
if (chars.length + 1 == i || value_i != null){
if (empty_chars > 0) {
System.out.print(String.format("%-" + empty_chars + "s", " "));
}
if (value_i != null){
System.out.print(String.format(node_format,value_i));
empty_chars = -1;
} else{
empty_chars = 0;
}
} else {
empty_chars++;
}
}
System.out.print("\n");
int depthToUse = Math.min(6,depth);
int line_offset = depthToUse - level;
line_offset *= 0.5;
line_offset = Math.max(0,line_offset);
for (int i=0;i<line_offset;i++){
System.out.println("");
}
level++;
}
}
private String[] getCharactersArray(List<PrintableNodePosition> nodes, int max_chars){
String[] positions = new String[max_chars+1];
for (PrintableNodePosition a : nodes){
int pos_i = maxColumnsLeft + a.column;
String title_i = a.nodeInfo.getTitleFormatted(this.maxTitleLength);
positions[pos_i] = title_i;
}
return positions;
}
}
NodeInfo class
package com.tomac120.NodePrinter;
/**
* Created by elijah on 6/28/16.
*/
public class PrintableNodeInfo {
public enum CLI_PRINT_COLOR {
RESET("\u001B[0m"),
BLACK("\u001B[30m"),
RED("\u001B[31m"),
GREEN("\u001B[32m"),
YELLOW("\u001B[33m"),
BLUE("\u001B[34m"),
PURPLE("\u001B[35m"),
CYAN("\u001B[36m"),
WHITE("\u001B[37m");
final String value;
CLI_PRINT_COLOR(String value){
this.value = value;
}
@Override
public String toString() {
return value;
}
}
private final String title;
private final PrintableNode leftChild;
private final PrintableNode rightChild;
private final CLI_PRINT_COLOR textColor;
public PrintableNodeInfo(String title, PrintableNode leftChild, PrintableNode rightChild){
this(title,leftChild,rightChild,CLI_PRINT_COLOR.BLACK);
}
public PrintableNodeInfo(String title, PrintableNode leftChild, PrintableNode righthild, CLI_PRINT_COLOR textColor){
this.title = title;
this.leftChild = leftChild;
this.rightChild = righthild;
this.textColor = textColor;
}
public String getTitle(){
return title;
}
public CLI_PRINT_COLOR getTextColor(){
return textColor;
}
public String getTitleFormatted(int max_chars){
return this.textColor+title+CLI_PRINT_COLOR.RESET;
/*
String title = this.title.length() > max_chars ? this.title.substring(0,max_chars+1):this.title;
boolean left = true;
while(title.length() < max_chars){
if (left){
title = " "+title;
} else {
title = title + " ";
}
}
return this.textColor+title+CLI_PRINT_COLOR.RESET;*/
}
public int getTitleLength(){
return title.length();
}
public PrintableNodeInfo getLeftChildInfo(){
if (leftChild == null){
return null;
}
return leftChild._getPrintableNodeInfo();
}
public PrintableNodeInfo getRightChildInfo(){
if (rightChild == null){
return null;
}
return rightChild._getPrintableNodeInfo();
}
}
NodePosition class
package com.tomac120.NodePrinter;
/**
* Created by elijah on 6/28/16.
*/
public class PrintableNodePosition implements Comparable<PrintableNodePosition> {
public final int row;
public final int column;
public final PrintableNodeInfo nodeInfo;
public PrintableNodePosition(PrintableNodeInfo nodeInfo, int row, int column){
this.row = row;
this.column = column;
this.nodeInfo = nodeInfo;
}
@Override
public int compareTo(PrintableNodePosition o) {
return Integer.compare(this.column,o.column);
}
}
And, finally, Node Interface
package com.tomac120.NodePrinter;
/**
* Created by elijah on 6/28/16.
*/
public interface PrintableNode {
PrintableNodeInfo _getPrintableNodeInfo();
PrintableNode _getLeftChild();
PrintableNode _getRightChild();
}
Source: Stackoverflow.com