How to print a tree in java?

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