Printing a Binary Tree: Solving the Space Issue

[brainTuner]

Hi, would you mind helping me in solving this problem?
Because I stuck now. The problem is to print a space in a binary tree (not binary search tree)
my current program can only output without appropriate spacing
so if input is : 4 7 8 9 2 0 3 1 5
the output will become
4
7 8
9 2 0 3
1 5

What the expected output is

             4
       7           8
    9    2      0    3
  1  5

actually the "/" space is not really compulsory, the problem is to print spaces

Here is my code contains 2 classes: TreeNode class and BinaryTree class

import java.io.*;
public class TreeNode 
{
    public Object da;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(Object newItem) 
    {
        da = newItem;
        left = null;
        right = null;
    }
    public TreeNode(Object newItem, TreeNode leftNode, TreeNode rightNode) 
    {
        da = newItem;
        left = leftNode;
        right = rightNode;
    }

    public void setItem(Object newItem) 
    { 
        da = newItem; 
    }
    public Object getItem() 
    { 
        return da; 
    }
    public void setLeft(TreeNode leftNode) 
    { 
        left = leftNode; 
    }
    public TreeNode getLeft() 
    { 
        return left; 
    }
    public void setRight(TreeNode rightNode) 
    { 
        right = rightNode; 
    }
    public TreeNode getRight() 
    { 
        return right; 
    }
    public int left (int i) 
    {  
        return 2*i;  
    } 
    public int right (int i) 
    {  
        return 2*i + 1;  
    } 
    public int parent (int i) 
    {  
        return (i-1)/2;
    }
}

import java.util.*;
 class BinaryTree
{
    
    public static void main(String args[])
    {
        Scanner input = new Scanner(System.in);
        System.out.println("Enter the values to insert into the binary tree: ");
        String[] values = (input.nextLine()).split("\\s");
    
    TreeNode root = null;
    Queue queue = new LinkedList();
    TreeNode parent = null;
    for (int index = 0; index < values.length; index++)
    {
        if (root == null)
        {
                root = new TreeNode(values[index]);
        queue.add(root);
        }
        else
        {
        TreeNode node = new TreeNode(values[index]);
        if (index % 2 == 1) {
            parent = (TreeNode) queue.remove();
            parent.setLeft(node);
        }

        else
        {
            parent.setRight(node);
        }
        queue.add(node);
        }
    }
    queue = new LinkedList();
    queue.add(root);
    int maxNodes = 1;
    int countNodes = 0;
    while (queue.size() > 0 )
    {
        TreeNode node = (TreeNode) queue.remove();
        
        System.out.print(node.getItem().toString() + " ");
        countNodes++;
        if (countNodes == maxNodes) 
        {
        System.out.println();
                maxNodes = maxNodes * 2;
        countNodes = 0;
        }
            TreeNode leftChild = node.getLeft();
        if (leftChild != null)
            queue.add(leftChild);
        TreeNode rightChild = node.getRight();
        if (rightChild != null)
            queue.add(rightChild);
    }
    System.out.println();
    }
}

It can’t print like the real binary tree and I do not know how to make it accordingly.
Any suggestions?
Thanks a lot. =)

 

[Mark44]

It seems to me that all you need to do is to print '\' and '/' characters, not spaces, in the appropriate places.

 

[brainTuner]

actually the "/" space is not really compulsory, the problem is to print spaces
my current program can only output without appropriate spacing
so if input is : 4 7 8 9 2 0 3 1 5
the output will become
4
7 8
9 2 0 3
1 5

What the expected output is

             4
       7           8
    9    2      0    3
  1  5

I also have edited my post above.
Thanks -)

 

[Mark44]

It's going to take a fair amount of code to do this, I think. When you print a line you have to take into account how many numbers will be printed on that line, or how many numbers could potentially be printed on that line.

Let's assume that the maximum width of a line is 80 characters. When you print the root of your tree (4), it needs to be printed in the middle of the line, or starting at position 40 in the line.

When you print the next line, with two numbers, you could print the first number 1/4 of the way across (at position 20), and the other number 3/4 of the way across (at position 60).

In the 3rd line, print values 1/8 of the way, 3/8 or the way, 5/8 of the way, and 7/8 of the way.
In the 4th line, print values 1/16, 3/16, 5/16, 7/16, 9/16, 11/16, 13/16, and 15/16 of the way.

Notice that in each line, numbers are being printed at odd multiples of 1/2ⁿ. The last row needs to be handled as a special case, because your tree might not be balanced, meaning that not all leaves in the bottom line have values. If the tree is balanced, line n will have 2^{n - 1} values. You need to have some logic so that when you are printing the nth line but have fewer than 2^{n - 1} values, you need to stop printing.

 

[brainTuner]

Actually I think it doesn't need to restrict the width of the line to 80 or any number.
it maybe looks something like this

               4                  --> to go to 4, needs 15 spaces
       5               2          --> to go to 5, needs 7 spaces (15 mod 2), then go to 2, needs 15 spaces
   1       8       9       2      --> to go to 1, needs 3 spaces (7 mod 2),then go to 8 needs 7 spaces,etc
 3                                --> to go to 3, needs 1 spaces (3 mod 1)

but since i use Que, the problem now is how to convert the Que to output the space, since I only know to do so, must use array, doesn't it?

 

[Filip Larsen]

Perhaps you can formulate a recursive function calculating the width of a node based on the width of its data and the widths of its children. Such a function could then be used to insert an appropriate amount of spaces.

Unless you are going to need your data structures for something else they may also be a bit overkill. An alternative data structure, which is often used as a compact tree structure in various algorithms, is to keep the elements in an array in the order specified by your input and just use simple functions that maps the array index of a node to the index of the left and right children.

 

[davee123]

Well, it seems like it's a little complex, but feasible, assuming you know something about your values. For starters, I don't know if it's safe to assume that all your values are single characters. That can start screwing you up if one of your values (particularly on the last rows) is, say, 65536.

So, really, the trick would be:

1) Determine the maximum depth of the tree, D.
2) Determine the width of your widest value, V.
3) Determine the "minimum" amount of space you want (e.g. the space between values on your last line), S

If my math is correct, for the Nth row of the printout, you need:
- The number of spaces to start the row: (V+S)*(2^(D-N)-1)/2 spaces
- The number of spaces to print between each value: (V+S)*(2^(D-N))-V

You could do this a couple ways, but I'd probably do it by traversing the tree depth-first, with left-most nodes, and build up an array of strings-- one for each line. Initialize each line with the appropriate amount of leading spaces. Then, traverse the tree. For each node at depth N, append the value to the string, using spaces to pad out the value to V characters (probably sprintf or what-have-you in Java). Then, append the appropriate number of spaces for that row.

If empty leaves are a problem, you can detect this at the point that a node is empty, and simply down-fill the lower rows with spaces using a similar technique, maybe even a recursive function to simply fill spaces up through the end row.

If traversing the tree is low-cost, and storing/appending to an array of strings is more cumbersome, you could always simply iterate through each row, printing the value out as you got to it, and traversing the tree EVERY time for each line you wanted to print. But that seems like it would be less efficient.

DaveE

 

[Filip Larsen]

I would like to repeat, that it is possible to make a fairly simple solution using recursion and the binary-tree-in-array structure I mention in #6. I got it done in 80 lines of Java code with most methods being very simple one-liner methods.

BrainTuner, if you can convince me that this is not homework (e.g. explain the reason why you need to solve this problem) I will post my solution. If it is homework, feel free to ask for more clues.

 

[Filip Larsen]

I assume it is now is safe to show code here without "spoiling" the homework for the original poster. So, in case anyone would be interested I have included what I ended up with below. As said earlier, most methods are one-liners, which in part is due to my fondness of the ?: operator. People who dislike this operator should have no trouble writing them out as if-else constructions.

import java.io.PrintStream;

/**
 * Example code for textual formatting an array of strings as a binary tree.
 * Internally, the tree is stored as an array with a fixed order of the nodes.
 * Uses recursion both up and down the tree to calculate textual width of each node.
 * 
 * @author Filip Larsen
 */
public class ArrayTree {
	
	public static void main(String[] args) {
		new ArrayTree("1 2 3 4 5 6 7 8 9 10 11 12 13 14 15").printTree();
		new ArrayTree("a b-with-some-more c d e-big f g h i j k l m n o p q").printTree();
		new ArrayTree("once upon a time there was three little pigs who lived in a house made out of steel reinforced concrete walls").printTree();
	}
	
	private final String[] data;
	private final int spacing = 1;
	private final PrintStream out = System.out;
	
	public ArrayTree(String data) {
		this(data.split("\\p{Space}+"));
	}
	
	public ArrayTree(String[] data) {
		this.data = data;
	}
	
	// Tree array access methods 
	
	/**
	 * Returns true if and only if a node is defined for the given index.
	 * Note, that isDefined(i) implies isDefined(j) for root <= j <= i.
	 */
	public boolean isDefined(int node) {
		return root() <= node && node < data.length; 
	}
	
	/**
	 * Returns the index of the root node.
	 */
	public int root() {
		return 0;
	}
	
	/**
	 * Returns the index of the left child of the given node.
	 */
	public int left(int node) {
		return 2*node+1;
	}
	
	/**
	 * Returns the index of the right child of the given node.
	 */
	public int right(int node) {
		return 2*node+2;
	}
	
	/**
	 * Returns the parent index for the given node.
	 */
	public int parent(int node) {
		return node > root() ? (node-1)/2 : root()-1;
	}
	
	// Width calculation methods
	
	/**
	 * Returns the combined width of the given left and right widths,
	 * adding the given spacing if both left and right width are positive. 
	 */
	public int space(int left, int space, int right) {
		return left + right + (left > 0 && right > 0 ? space : 0);
	}
	
	/**
	 * Returns the with of the given node, which must be defined.
	 */
	public int nodeWidth(int node) {
		return data[node].length();
	}
	
	/**
	 * Recursively calculate the combined with of a nodes left and right sub-tree.
	 */
	public int childWidth(int node) {
		return space(treeWidth(left(node)), spacing, treeWidth(right(node)));
	}

	/**
	 * Recursively calculate the maximum width of a node and its children. 
	 */
	public int treeWidth(int node) {
		return isDefined(node) ? Math.max(nodeWidth(node), childWidth(node)) : 0;
	}
	
	/**
	 * Recursive calculate by how much a parent of right-nodes is wider than its children.
	 * Used to right-adjust the tree of right-nodes relative to their parent.
	 */
	public int excessWidth(int node) {
		final int p = parent(node);
		return node == root() ? 0 : node == right(p) ? nodeWidth(p) - childWidth(p) : excessWidth(p);
	}
	
	// Formatting methods 
	
	/**
	 * Prints the given node with left and right padding to ensure proper alignment of sub-trees.
	 * This method will align the node text over the center of the gap between the left and right 
	 * sub-tree, if both are present.
	 */
	public void printNode(int node) {
		pad(excessWidth(node));
		final int w = nodeWidth(node);
		final int lw = treeWidth(left(node));
		final int cw = childWidth(node);
		// Note that cw > lw always holds when the node has both a left and right sub-tree. 
		// First, calculate padding in order to center node text above center gap.
		int lpad = Math.max(0, cw > lw ? lw + spacing/2 - w/2 : (cw-w)/2);
		int rpad = Math.max(0, cw - lpad - w);
		// Second, adjust this to keep left/right padding as balanced as possible 
		// while still keeping the node text over the center gap.
		if (cw > lw) {
			int a = Math.min(Math.max(-(w-1)/2, (rpad - lpad)/2), (w-1)/2);
			lpad += a;
			rpad -= a;
		}
		pad(lpad);
		out.print(data[node]);
		pad(rpad + spacing);
	}
	
	/**
	 * Prints one line of the tree, starting with the given node as left-most node.
	 */
	public void printLevel(int node) {
		for (int n = node; isDefined(n) && n < left(node); n++) {
			printNode(n);
		}
		out.println();
	}
	
	/**
	 * Prints the whole tree as lines starting with the root node.
	 */
	public void printTree() {
		for (int n = root(); isDefined(n); n = left(n)) {
			printLevel(n);
		}
		out.println();
	}
	
	public void pad(int n) {
		pad(n, ' ');
	}
	
	public void pad(int n, char ch) {
		for (int i = 0; i < n; i++) out.print(ch);
	}
}