# Printing a binary tree in vertical strips

I'm trying to print a binary tree in vertical strips.

For instance, a tree like this:

       8
/   \
6     10
/ \   /  \
4   7 9    12
/ \
3   5


Is printed out as:

3
4
6 5
8 7 9
10
12


Here's how I'm doing it:

Map<Integer,Set<Integer>>  printStripsVertically(TreeNode root, Map<Integer,Set<Integer>> countMap, int dist) {

if( root == null )
return countMap;

Set<Integer> nodeSet = countMap.get(dist);// get list at current distance.

if(nodeSet ==null) { // this dist  hasnt been inspected yet, so create new list here.
nodeSet= new HashSet<Integer>();
}

countMap.put(dist,nodeSet);// create mapping for current dist
//recurse left and right.

Map<Integer,Set<Integer>> leftMap = printStripsVertically(root.getLeft(),countMap,dist-1);
Map<Integer,Set<Integer>> rightMap = printStripsVertically(root.getRight(),countMap,dist+1);
Map<Integer,Set<Integer>> mergedMap= new HashMap<Integer,Set<Integer>>();
Iterator<Integer> itLeft = leftMap.keySet().iterator();
while(itLeft.hasNext()){
mergedMap.put(itLeft.next(),leftMap.get(itLeft.next()));
}
Iterator<Integer> itRight = rightMap.keySet().iterator();
while(itRight.hasNext()){
mergedMap.put(itRight.next(),rightMap.get(itRight.next()));
}

return mergedMap;//iterate over the map to get results.
}


Edit : TreeNode.java

public class TreeNode {

int data;
private TreeNode left;
private TreeNode right;
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}

public TreeNode(int data)
{
this.data=data;
}

}


Call to the method

 Map<Integer,Set<Integer>> verticalStrips = new HashMap<Integer,Set<Integer>>();
verticalStrips =printStripsVertically(root,verticalStrips,0);//where root is the root of the tree.


I've dry-tested the algorithm to work, but I'm not quite convinced that iterating over the leftMap and rightMap is the cleanest way to go about this, so I'm looking for any suggestions towards that in particular or the code in general.

Any thoughts on its correctness are appreciated. I'm also looking for any other approaches that might be more efficient in dealing with the problem.

• Could you provide a code example of how you call this method? And how the TreeNode class looks Jul 29, 2015 at 21:01
• The challenge you are solving is the same as the one in this question. As I remarked there, I believe that the challenge is poorly defined: What if "7" has two complete levels under it? I think you would probably consider the left child of "7" to share the same column as "5". What about the leftmost grandchild of "7"? Would it be to the left of "5"? That doesn't make sense. Jul 29, 2015 at 21:03
• @200_success: Thanks for the comment. However, since 7 and 9 share the same level as their parent I think, the leftmost grandchild of "7" would share the same level as "4". Jul 29, 2015 at 21:42
• @SimonAndréForsberg : Added details. Jul 29, 2015 at 21:51