Printing a tree level by level

Question

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.value) {
            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
    Queue<Node> nodes= new LinkedList<>(); 

    List<Node> listOfNodes = new ArrayList<Node>();
    //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.size()){
        int printLen= (int) Math.pow(2, level++);

        for (int i=count; i < printLen -1 && i < listOfNodes.size();++i){
            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, List<Node> listOfNodes, Queue<Node> nodes) {
    // TODO Auto-generated method stub
    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?

Answer 1

Is this the correct method?

No. You are trying to derive the level number from a flat list of nodes and some power of 2. This will only work with a complete balanced binary search tree, and you didn't mention such requirements to be present. To see a bad example, insert -4 to your existing sample. The resulting tree:

            5 
        1      8 
     -2   3   6 9 
   -3 -1
-4

The output of your program:

5 
1 8 
-2 3 6 9 
-3 -1 -4

As you see, -4 is printed at the wrong level. This is because when you flatten the tree to a list of nodes, you lose important information about the structure, and you cannot derive the levels using math.

To fix this, you cannot flatten the tree to a list, you need a list-of-lists.

Is there any more efficient method?

There are several other efficiency and coding style problems in the existing. Let's start from there and work our ways to an improved and correct solution.

Encapsulation

The point of encapsulation is hiding implementation details. The printLevelWise method is a user of the traverseLevels method, but it knows too much about how it works:

Queue<Node> nodes= new LinkedList<>(); 
List<Node> listOfNodes = new ArrayList<Node>();
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, initialize 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<Node> 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<Node> 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 thinking in traverseLevels. Here's one ay 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<List<Node>> traverseLevels(Node root) {
    if (root == null) {
        return Collections.emptyList();
    }
    List<List<Node>> levels = new LinkedList<>();

    Queue<Node> nodes = new LinkedList<>();
    nodes.add(root);

    while (!nodes.isEmpty()) {
        List<Node> 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 straighforward:

public void printLevelWise(Node root) {
    List<List<Node>> levels = traverseLevels(root);

    for (List<Node> 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