How to print a tree in java?
I have written a program to print a binary tree level by level on different lines, like the tree would actually look if drawn on paper.
I have done a BFS traversal and then I proceed to print the tree assuming it is complete binary tree:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class BinaryTreeLevelWise {
/**
* This class represents the individual nodes of the binary tree
* Each node has a left, right pointer of type Node
* and Value to hold the value
* @author Aneesh
*
*/
class Node {
Node left;
Node right;
int value;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node value=" + value + "";
}
}
/**
* Driver function to test the code
* @param args
*/
public static void main(String[] args) {
new BinaryTreeLevelWise().run();
}
/**
* This function inserts an element into the binary tree
* @param node
* @param value
*/
public void insert(Node node, int value) {
if (value < node> if (node.left != null) {
insert(node.left, value);
} else {
System.out.println(" Inserted " + value + " to left of "
+ node.value);
node.left = new Node(value);
}
} else if (value > node.value) {
if (node.right != null) {
insert(node.right, value);
} else {
System.out.println(" Inserted " + value + " to right of "
+ node.value);
node.right = new Node(value);
}
}
}
/**
* Builds the tree and executes some functions
*/
public void run() {
// build the simple tree from chapter 11.
Node root = new Node(5);
System.out.println("Binary Tree Example");
System.out.println("Building tree with root value " + root.value);
insert(root, 1);
insert(root, 8);
insert(root,-2);
insert(root, 6);
insert(root, 3);
insert(root, 9);
insert(root,-3);
insert(root,-1);
/*System.out.println("Traversing tree in order");
printInOrder(root);
System.out.println("Traversing tree front-to-back from location 7");
printFrontToBack(root, 7);*/
System.out.println("*************nPrinting the tree levelWise");
printLevelWise(root);
}
/**
* This functions uses a list of nodes and prints them level wise assuming a complete
* binary tree.
* Every level will have have 2^L elements where L is the level, root is level L=0
* @param Root of the tree of type {@link Node}
*/
public void printLevelWise(Node root) {
// TODO Auto-generated method stub
Queuenodes= new LinkedList<>();
ListlistOfNodes = new ArrayList //add root to the list();
traverseLevels(root, listOfNodes,nodes);
//printing in a straight line
//System.out.println("nodes are "+listOfNodes);
// printing level wise
int count = 0,level=0;
while (count < listOfNodes> int printLen= (int) Math.pow(2, level++);
for (int i=count; i < printLen> System.out.print(listOfNodes.get(i).value+" ");
}
System.out.println();
count = printLen-1;
}
}
/**
* This function traverses the tree and puts all the nodes level wise into a list
* @param root
* @param listOfNodes
* @param nodes
*/
private void traverseLevels(Node root, ListlistOfNodes, Queue // TODO Auto-generated method stubnodes) {
if (root!=null){
nodes.add(root);
listOfNodes.add(root);
while(!nodes.isEmpty()){
//standard BFS
root= nodes.poll();
if (root.left!=null) {
listOfNodes.add(root.left);
nodes.add(root.left);
}
if (root.right!=null) {
listOfNodes.add(root.right);
nodes.add(root.right);
}
}
}
}
}
Output:
5
1 8
-2 3 6 9
-3 -1
Is this the correct method? Are there any more efficient methods?
The answer to your question - how to print a tree in java is -
Code Review
Printing a tree level by level
Asked 7 years, 1 month ago
Modified 3 years, 11 months ago
Viewed 40k times
6
2
I have written a program to print a binary tree level by level on different lines, like the tree would actually look if drawn on paper.
I have done a BFS traversal and then I proceed to print the tree assuming it is complete binary tree:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class BinaryTreeLevelWise {
/**
* This class represents the individual nodes of the binary tree
* Each node has a left, right pointer of type Node
* and Value to hold the value
* @author Aneesh
*
*/
class Node {
Node left;
Node right;
int value;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node value=" + value + "";
}
}
/**
* Driver function to test the code
* @param args
*/
public static void main(String[] args) {
new BinaryTreeLevelWise().run();
}
/**
* This function inserts an element into the binary tree
* @param node
* @param value
*/
public void insert(Node node, int value) {
if (value < node xss=removed xss=removed> node.value) {
if (node.right != null) {
insert(node.right, value);
} else {
System.out.println(" Inserted " + value + " to right of "
+ node.value);
node.right = new Node(value);
}
}
}
/**
* Builds the tree and executes some functions
*/
public void run() {
// build the simple tree from chapter 11.
Node root = new Node(5);
System.out.println("Binary Tree Example");
System.out.println("Building tree with root value " + root.value);
insert(root, 1);
insert(root, 8);
insert(root,-2);
insert(root, 6);
insert(root, 3);
insert(root, 9);
insert(root,-3);
insert(root,-1);
/*System.out.println("Traversing tree in order");
printInOrder(root);
System.out.println("Traversing tree front-to-back from location 7");
printFrontToBack(root, 7);*/
System.out.println("*************
Printing the tree levelWise");
printLevelWise(root);
}
/**
* This functions uses a list of nodes and prints them level wise assuming a complete
* binary tree.
* Every level will have have 2^L elements where L is the level, root is level L=0
* @param Root of the tree of type {@link Node}
*/
public void printLevelWise(Node root) {
// TODO Auto-generated method stub
Queue nodes= new LinkedList<>();
List listOfNodes = new ArrayList();
//add root to the list
traverseLevels(root, listOfNodes,nodes);
//printing in a straight line
//System.out.println("nodes are "+listOfNodes);
// printing level wise
int count = 0,level=0;
while (count < listOfNodes xss=removed i=count; xss=removed root!=null){ xss=removed root.left!=null) root.right!=null) xss=removed>();
List listOfNodes = new ArrayList();
traverseLevels(root, listOfNodes,nodes);
printLevelWise is passing a Queue to the method, but printLevelWise itself doesn't use this queue. The fact that traverseLevels uses a queue is an implementation detail, printLevelWise shouldn't have to know about it. Remove this parameter, initialise it inside traverseLevels, where it's actually used.
void method with out-parameter
The traverseLevels method is practically a void method with an out-parameter List that it populates. In many practical cases, including your program in question, a better option is to make the method return the out-parameter as its result.
Move common logic to higher level
In this code:
listOfNodes.add(root);
while(!nodes.isEmpty()){
root= nodes.poll();
if (root.left!=null) {
listOfNodes.add(root.left);
nodes.add(root.left);
}
if (root.right!=null) {
listOfNodes.add(root.right);
nodes.add(root.right);
}
}
You add the root to listOfNodes, and then add the branches. That is, you are adding to the list at 3 places. You could refactor this to add to the list at once place, right after polling:
while (!nodes.isEmpty()) {
root = nodes.poll();
listOfNodes.add(root);
if (root.left != null) {
nodes.add(root.left);
}
if (root.right != null) {
nodes.add(root.right);
}
}
This is simpler, shorter, and the outcome is equivalent.
Bad comments
These are bad comments:
// TODO Auto-generated method stub
Queue nodes= new LinkedList<>();
//add root to the list
traverseLevels(root, listOfNodes,nodes);
Auto-generated comments should be removed the moment you start adding implementation.
The second comment is a blatant lie. The next line has nothing to do with adding root to the list.
Preserving the levels
To preserve the levels, you need a different way of thinking in traverseLevels. Here's one way to solve this:
In every cycle of !nodes.isEmpty()
Copy and consume all the nodes currently in the queue
Add the non-null children of the nodes to the queue
This way, every cycle will correspond to one level
Implementation:
private List> traverseLevels(Node root) {
if (root == null) {
return Collections.emptyList();
}
List> levels = new LinkedList<>();
Queue nodes = new LinkedList<>();
nodes.add(root);
while (!nodes.isEmpty()) {
List level = new ArrayList<>(nodes.size());
levels.add(level);
for (Node node : new ArrayList<>(nodes)) {
level.add(node);
if (node.left != null) {
nodes.add(node.left);
}
if (node.right != null) {
nodes.add(node.right);
}
nodes.poll();
}
}
return levels;
}
Using the rewritten traverseLevels, the implementation of printLevelWise becomes straightforward:
public void printLevelWise(Node root) {
List> levels = traverseLevels(root);
for (List level : levels) {
for (Node node : level) {
System.out.print(node.value + " ");
}
System.out.println();
}
}
And produces the correct output:
5
1 8
-2 3 6 9
-3 -1
-4
Answer (1)
Printing a tree in Java typically involves traversing the tree and printing the nodes in a structured format. Here’s a step-by-step guide on how to print a binary tree in Java:
1. Define the Tree Node Class
First, you need a class to represent each node in the tree. Here's a basic example for a binary tree node:
class TreeNode { int value; TreeNode left; TreeNode right; TreeNode(int value) { this.value = value; left = null; right = null; }}2. Define the Tree Structure and Traversal Methods
You will need methods to traverse the tree. Common traversal methods are in-order, pre-order, and post-order. For printing, in-order traversal is often used.
In-Order Traversal Method:
void inOrderTraversal(TreeNode node) { if (node != null) { inOrderTraversal(node.left); // Visit left subtree System.out.print(node.value + " "); // Visit node inOrderTraversal(node.right); // Visit right subtree }}3. Print the Tree Structure
To print the tree structure in a visually understandable way, you can use a depth-first approach with indentation to represent levels.
Print Tree Structure Method:
void printTree(TreeNode node, String prefix, boolean isLeft) {
if (node != null) { System.out.println(prefix + (isLeft ? "├── " : "└── ") + node.value); printTree(node.left, prefix + (isLeft ? "│ " : " "), true); printTree(node.right, prefix + (isLeft ? "│ " : " "), false); }}4. Example Usage
Here is how you can create a tree, and use the methods to print it:
public class BinaryTree { public static void main(String[] args) { // Create the tree nodes TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.left = new TreeNode(6); root.right.right = new TreeNode(7); // Print in-order traversal System.out.print("In-Order Traversal: "); inOrderTraversal(root); System.out.println(); // Print tree structure System.out.println("Tree Structure:"); printTree(root, "", true); } // In-Order Traversal Method static void inOrderTraversal(TreeNode node) { if (node != null) { inOrderTraversal(node.left); System.out.print(node.value + " "); inOrderTraversal(node.right); } } // Print Tree Structure Method static void printTree(TreeNode node, String prefix, boolean isLeft) { if (node != null) { System.out.println(prefix + (isLeft ? "├── " : "└── ") + node.value); printTree(node.left, prefix + (isLeft ? "│ " : " "), true); printTree(node.right, prefix + (isLeft ? "│ " : " "), false); } }}Explanation:
- TreeNode Class: Defines the structure of a node in the tree.
- inOrderTraversal Method: Prints the nodes in in-order traversal (left, root, right).
- printTree Method: Prints the tree structure visually with branches representing the hierarchy.
- BinaryTree Class: Contains the main method, creates a sample tree, and demonstrates the traversal and printing methods.
By using the above methods, you can easily print a tree in Java both in in-order traversal and in a structured tree format.
5 Months