Leetcode 662: maximum width of binary tree in Java

Question

I have the following solution to this problem. The idea is to compute the maximum width of a binary search tree. The width of a BST on a particular depth is defined as the distance from the leftmost non-null node to the rightmost non-null node at that depth. This implementation proceeds downwards from the root node in breadth-first manner keeping track of the width of the widest tree level until an empty level is encountered. (Note that the widest level isn’t necessarily the deepest one.

class TreeNode { int val; int num; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } class Solution { public int widthOfBinaryTree(TreeNode root) { TreeNode[] levelHi = new TreeNode[3_000]; TreeNode[] levelLo = new TreeNode[3_000]; levelHi[0] = root; root.num = 0; int maximumWidth = 1; int levelLength = 1; while (true) { int numberOfChildrenInLoLevel = getNextDeepestLevel(levelHi, levelLo, levelLength); if (numberOfChildrenInLoLevel == 0) { return maximumWidth; } int tentativeWidth = levelLo[numberOfChildrenInLoLevel - 1].num - levelLo[0].num + 1; maximumWidth = Math.max(maximumWidth, tentativeWidth); TreeNode[] levelTemp = levelLo; levelLo = levelHi; levelHi = levelTemp; levelLength = numberOfChildrenInLoLevel; } } int getNextDeepestLevel(TreeNode[] levelHi, TreeNode[] levelLo, int levelHiLength) { int levelLoLength = 0; for (int i = 0; i < levelHiLength; i++) { TreeNode currentTreeNode = levelHi[i]; TreeNode leftChild = currentTreeNode.left; TreeNode rightChild = currentTreeNode.right; if (leftChild != null) { leftChild.num = currentTreeNode.num * 2; levelLo[levelLoLength++] = leftChild; } if (rightChild != null) { rightChild.num = currentTreeNode.num * 2 + 1; levelLo[levelLoLength++] = rightChild; } } return levelLoLength; } } 

Critique request

I would like to hear comments about efficiency and space consumption.

Answer 1

I'll just mention doc comments,
and that you added an instance data member num to TreeNode as provided by LeetCode.

The code has illuminative names for most everything, but uses one magic number: 3000.

getNextDeepestLevel() has code duplicated in handling left and right child.
Not trivial to avoid in a language not supporting data aliasing
(C++: TreeNode children[2], &left = children[0], &right = children[1];),
but modifying TreeNode, anyway, one might implement Iterable. (I'll have to revisit AspectJ.)

Efficiency:
With the information provided in LeetCode 662, every node needs to be visited. With considerable overhead, I think it possible to reduce that to ⅔
• keeping a count of nodes in levels traversed and
• making use of knowledge about the tree's total number of nodes.
(What information would be needed to just follow left and right boundaries?
node height may help.)

Space consumption:
Each of the "level arrays" will need to keep no more than the maximum number of nodes per level -
which, for a binary tree, is bounded by \$\lceil \frac{\#nodes}2 \rceil\$.
For every other node added to levelLo, there is one node from levelHi no longer needed:
One can "overlay the arrays", e.g., filling from the high index end consuming nodes from lower index to zero, reversing roles&directions between passes/levels.
Or add not keeping leaf nodes to the picture, reducing the number of nodes kept per level to no more than one third of their total number. (And impeding code simplicity/brevity/readability: maintainability.)
dariosicily mentioned using a queue (the usual way of handling level order) - the number of nodes to handle in any given level is the size of the queue just after consuming the last node of the level before.

You are aware of iterative deepening.
When not keeping nodes with less than two children (and keeping the depth of nodes), this reduces additional space to \$O(\log n)\$ - increasing time drastically (to \$O(N^2)\$?).