Finding the width of a binary tree

Question

Finding the width of a binary tree.

In my code for each vacation, I create a hash map entry and continue to update it when I find node when i exit. I will finally iterate over the hash map to find the maximum width. But how can I do this without using any class / global varleables?

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 a HashMap inside the method, and then move all the work to a helper method, for example:

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

Answer 2

You do not need to track the number of nodes per level.

Define the horizontal position of each node as the number of correct children minus the number of left children that have been traversed from root to node. Then the width will be the maximum horizontal position minus the minimum horizontal position. Min / max positions can be passed around a recursive traversal in an array of two components.

Here is a sample code that I have in mind:

 int getWidth(Node node) { // current[0] is the number of left children traversed of the current path // current[1] is the number of right children traversed of the current path int[] current = { 0, 0 }; // extremes[0] is the minimum horizontal position // extremes[1] is the maximum horizontal position int[] extremes = { 0, 0 }; computeExtremes(node, current, extremes); return (extremes[1] - extremes[0]); } void computeExtremes(Node node, int[] current, int[] extremes) { if (node == null) { return; } int position = current[1] - current[0]; if (extremes[0] > position) { extremes[0] = position; } if (extremes[1] < position) { extremes[1] = position; } current[0]++; computeExtremes(node.left, current, extremes); current[0]--; current[1]++; computeExtremes(node.right, current, extremes); current[1]--; } 

Answer 3

If I understand correctly, do you want to do something like this?

 public Map<Integer,Integer> width( Node node ) { Map<Integer,Integer> mp = new HashMap<Integer,Integer>(); width( node, 1, mp ); return mp; } private void width( Node node, int level, Map<Integer,Integer> mp ) { 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 4

This uses @nathan algo, but passes by value.

 Pair<int, int> extremes(Node node, int x, int y) { if (node == null) return makePair(x,y); Pair p1 = extremes(node.left, x-1, y); Pair p2 = extremes(node.right, x, y+1); return makePair(min(p1.x, p2.x), max(p1.y, p2.y)) } 

Answer 5

See https://www.geeksforgeeks.org/maximum-width-of-a-binary-tree/

Use recursive with hash table

 int getWidth(struct node* root, int level) { if(root == NULL) return 0; if(level == 1) return 1; else if (level > 1) return getWidth(root->left, level-1) + getWidth(root->right, level-1); } 

Use a queue to remove a parent and replace with child nodes

 static int maxwidth(node root) { // Base case if (root == null) return 0; // Initialize result int maxwidth = 0; // Do Level order traversal keeping // track of number of nodes at every level Queue<node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { // Get the size of queue when the level order // traversal for one level finishes int count = q.size(); // Update the maximum node count value maxwidth = Math.max(maxwidth, count); // Iterate for all the nodes in // the queue currently while (count-- > 0) { // Dequeue an node from queue node temp = q.remove(); // Enqueue left and right children // of dequeued node if (temp.left != null) { q.add(temp.left); } if (temp.right != null) { q.add(temp.right); } } } return maxwidth; } 

Answer 6

Something a little different:

 int[] width(Node node){ if(node==null) { return new int[]{}; } int[] la = width(node.left); int[] ra = width(node.right); return merge(1, la, ra); } private int[] merge(int n0, int[] la, int[] ra) { int maxLen = Math.max(la.length, ra.length); int[] result = new int[maxLen+1]; result[0] = n0; for (int i = 0; i < maxLen; ++i) { result[i+1] = i >= la.length ? ra[i] : i >= ra.length ? la[i] : la[i] + ra[i]; } return result; }