Problem

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.

Solution

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 ⌈#nodes2⌉

.

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(logn)

– increasing time drastically (to O(N2)

$O({N}^{2})$?).