2
\$\begingroup\$

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>();
        }

        nodeSet.add(root.data);// add current node to list. 
        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.

\$\endgroup\$
  • \$\begingroup\$ Could you provide a code example of how you call this method? And how the TreeNode class looks \$\endgroup\$ – Simon Forsberg Jul 29 '15 at 21:01
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – 200_success Jul 29 '15 at 21:03
  • \$\begingroup\$ @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". \$\endgroup\$ – seeker Jul 29 '15 at 21:42
  • \$\begingroup\$ @SimonAndréForsberg : Added details. \$\endgroup\$ – seeker Jul 29 '15 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.