Finding the max width of the tree

Question

     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<T> {

    private TreeNode<T> root;

    public MaxWidthOfTree(List<T> items) {
        create(items);
    };


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

        root = new TreeNode<>(items.get(0));

        final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
        queue.add(root);

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

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

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

    private static class TreeNode<T> {
        private TreeNode<T> left;
        private T item;
        private TreeNode<T> 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 < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }


    private void computeWidth(TreeNode<T> 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<T> node) {
        if (node == null) return -1;
        return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }
}

public class MaxWidthOfTreeTest {

    @Test
    public void testLevel3() {
        MaxWidthOfTree<Integer> mwot1 = new MaxWidthOfTree<>(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<Integer> mwot2 = new MaxWidthOfTree<>(Arrays.asList(1, 2, 3, 4, 5, null, 7, null, null, 14, 15, null, null, 16, 17));
        assertEquals(4, mwot2.getMaxWidth());
    }
}

Answer 1

The most logical solution to this problem is to do a BFS (Breadth-First-search) and then determine the size of each level as you get to it.

Your solution uses a depth-first search and tracks the results in an array. But, to create the array, it has to calculate the depth too.

If you have to do it that way, then you should calculate the values in an ArrayList instead, and avoid the height calculation first.

The breadth-first algorithm would be simple:

public int getMaxWidth(Node root) {
    Queue<Node> row = new LinkedList<>();
    row.add(root);
    row.add(null); // use null as a marker for the end of a row.
    int maxwidth = 1;
    while (!row.isEmpty()) {
        Node n = row.remove();
        if (n == null) {
            // next row
            int rowsize = row.size();
            if (rowsize > 0) {
                if (rowsize > maxwidth) {
                    maxwidth = rowsize;
                }
                row.add(null); // add new end-of-row-marker.
            }
        } else {
            if (n.left != null) {
                row.add(n.left);
            }
            if (n.right != null) {
                row.add(n.right);
            }
        }
    }
    return maxwidth;
}

This way you are restricted to a simple, single scan of your tree, with just a single row's worth of data pointers as memory overhead. \$O(n)\$ time and space complexity.

Answer 2

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 //<--- 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.

Answer 3

You could make your computeWidth() method completely independent from precomputing the "height" of the tree. (minor nitpick: trees are deep and not high).

If performance (and stackframes) is not an issue it's simply a matter of making the function run recursively.

private int computeWidth (TreeNode<?> currentNode, final Map<Integer, Integer> data, int currentLevel) {
    if (currentNode == null) {
        if (currentLevel == ROOT_LEVEL) {
             throw new IllegalArgumentException("Root node mustn't be null");
        }
        return; //early return, dead end
    }
    final Integer width = data.get(currentLevel);
    data.put(currentLevel, (width == null) ? 1 : width + 1); //increment width for current level
    computeWidth(currentNode.left, data, currentLevel + 1);
    computeWidth(currentNode.right, data, currentLevel + 1);

    return Collections.max(data.values());
}

The idea of this is quite simple. You can store the width of a level in a map, independant of the method you call. You then recursively traverse down the tree, while incrementing a counter you pass with it.

This counter is parallel (or even equivalent) to the depth of the stackframe you are currently in.

The line data.put is quite hackish, it makes use of boxing and implicit conversions to make a non-existant level in the map not throw NPE's. (null Integers get converted to 0 when casting to primitive int)

You'd initially call using following line:

int maxWidth = computeWidth(root, new HashMap<Integer, Integer>(), ROOT_LEVEL);

This way you completely eliminate one n from the big O notation, because you can avoid the precalculation of height, which reduces the timecomplexity from intially \$O(n^3)\$ to just \$O(n^2)\$ in your class because (as mentioned by Pimgd) you traverse all input elements to create the tree.

Additionally this approach should also work for any possible Tree passed into it, given you adjust the internal recursive working of computeWidth to traverse all branches of a node.