Finding the max width of the tree 1
    /  \
   2    3
 /  \     \
4    5     8 
          /  \
         6    7

  
  Width of a tree is maximum of widths of all levels.
  
  For the above tree:
  
  
  width of level 1 is 1
  width of level 2 is 2
  width of level 3 is 3
  width of level 4 is 2
  
  
  So the maximum width of the tree is 3.


This code is attributed to GeeksForGeeks. I'm looking for code-review, best practices and optimizations. I'm verifying space complexity to be \$O(n)\$.

public class MaxWidthOfTree&lt;T&gt; {

    private TreeNode&lt;T&gt; root;

    public MaxWidthOfTree(List&lt;T&gt; items) {
        create(items);
    };


    private void create(List&lt;T&gt; items) {
        if (items.isEmpty())  {
            throw new NullPointerException("The input array is not empty.");
        }

        root = new TreeNode&lt;&gt;(items.get(0));

        final Queue&lt;TreeNode&lt;T&gt;&gt; queue = new LinkedList&lt;TreeNode&lt;T&gt;&gt;();
        queue.add(root);

        final int half = items.size() / 2;

        for (int i = 0; i &lt; half; i++) {
            if (items.get(i) != null) {
                final TreeNode&lt;T&gt; current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (items.get(left) != null) {
                    current.left = new TreeNode&lt;&gt;(items.get(left));
                    queue.add(current.left);
                }
                if (right &lt; items.size() &amp;&amp; items.get(right) != null) {
                    current.right = new TreeNode&lt;&gt;(items.get(right));
                    queue.add(current.right);
                }
            }
        }
    }

    private static class TreeNode&lt;T&gt; {
        private TreeNode&lt;T&gt; left;
        private T item;
        private TreeNode&lt;T&gt; right;

        TreeNode(T item) {
            this.item = item;
        }
    }

    public int getMaxWidth() {
        if (root == null) {
            throw new IllegalArgumentException("The root is empty");
        }

        int h = getHeight(root);
        int[] arr = new int[h + 1]; // NOTE: h + 1

        computeWidth(root, arr, 0);

        return maxElementOfArray (arr);
    }


    private int maxElementOfArray(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i &lt; arr.length; i++) {
            if (arr[i] &gt; max) {
                max = arr[i];
            }
        }
        return max;
    }


    private void computeWidth(TreeNode&lt;T&gt; node, int[] arr, int level) {
        if (node == null) return;
        arr[level]++;  // NOTE: you can place this as preorder, inorder or postorder, does not matter.
        computeWidth(node.left, arr, level + 1);
        computeWidth(node.right, arr, level + 1);
    }


    public int getHeight(TreeNode&lt;T&gt; node) {
        if (node == null) return -1;
        return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }
}

public class MaxWidthOfTreeTest {

    @Test
    public void testLevel3() {
        MaxWidthOfTree&lt;Integer&gt; mwot1 = new MaxWidthOfTree&lt;&gt;(Arrays.asList(1, 2, 3, 4, 5, null, 7, null, null, null, null, null, null, 14, 15));
        assertEquals(3, mwot1.getMaxWidth());
    }

    @Test
    public void testTestLevel4() {
        MaxWidthOfTree&lt;Integer&gt; mwot2 = new MaxWidthOfTree&lt;&gt;(Arrays.asList(1, 2, 3, 4, 5, null, 7, null, null, 14, 15, null, null, 16, 17));
        assertEquals(4, mwot2.getMaxWidth());
    }
}
Similar code, so similar answer.

Please take these things to heart; I feel like I'm wasting my time otherwise.

    return maxElementOfArray (arr);


You have a space between the function name and the parentheses.

Finalize your arguments if you're not gonna do anything with them. Final your locals if you're not gonna do anything with them.



I feel your approach is completely wrong. Why load the whole tree structure into memory? Because you're copying the same code over and over. And that turns you into a blind programmer.

Instead, try this:

Add depth to TreeNode. private int depth;

Add depth to the constructor of TreeNode as the second argument.

Then declare root to be at depth 1.

Declare an array of int (we'll call it widths). Size 32; you can't get deeper with your syntax for defining a tree. (Maybe you can, I'm not sure how well a list containing 2^32 items will function).

Next, parse the list.

Whenever you add a new node to the queue, widths[current.depth+1]++. Whenever you create a new node, pass current.depth+1 as the second argument.

When you're done parsing the list, return maxElementOfArray(widths).

That might be considered cheating though; we're not really using a tree. Anyway.



    if (items.isEmpty())  {
        throw new NullPointerException("The input array is not empty.");
    }


Erm... yes it is. Maybe "The input list shouldn't be empty". Also NullPointerException is NOT valid here; use IllegalArgumentException instead (I didn't pass null! I passed empty list! If I get NullPointerException back when I pass in non-null objects then I spend a lot of time debugging, trying to find my null.)

    int h = getHeight(root);
    int[] arr = new int[h + 1]; // NOTE: h + 1


Use int height, it's more descriptive. Get rid of the comment or write WHY. Right now it could have been //&lt;--- important! too, and that doesn't help anyone. Maybe consider using int[] arr = new int[getHeight(root) + 1]; as you don't reuse this h anywhere.

Your maxElementOfArray function returns Integer.MIN_VALUE. There's no such thing as a negative width. Return 0 instead; the top level contains 0 items. There are no other levels.

You perform three traversals of the entire tree; create is one, getHeight is two, computeWidth is three. I'd combine getHeight and computeWidth. You'll have to rewrite a couple things for this... but I believe I gave some pointers already.