finding the width of a binary tree

Question

Finding the width of binary tree.

In my code for each leave i create a entry in a hash map and keep updating it when i found a node at leave i.Finally i will iterate the hashmap to find max width.But how can i do it without using any classleel/global varaiables?

Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
void width(Node node,int level){
        if(node==null)
            return;
        if(mp.containsKey(level)){
            int count = mp.get(level);
            mp.put(level, count+1);
        }else{
            mp.put(level, 1);
        }

        width(node.left, level+1);
        width(node.right, level+1);

    }

Answer 1

Just create the HashMap inside the method, then move all the work into an auxillary method, like this:

void width(Node node,int level){
    Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
    widthImpl(mp, node, level);
    // find maximum
}

private void widthImpl(Map<Integer,Integer> mp, Node node, int level) {
    if(node==null)
        return;
    if(mp.containsKey(level)){
        int count = mp.get(level);
        mp.put(level, count+1);
    }else{
        mp.put(level, 1);
    }

    widthImpl(mp, node.left, level+1);
    widthImpl(mp, node.right, level+1);
}