# [C++/Java] * [BFS/DFS/3liner] Clean Code With Explanation

• The idea is to use heap indexing:

``````        1
2         3
4   5     6   7
8 9 x 11  x 13 x 15
``````

Regardless whether these nodes exist:

• Always make the id of left child as `parent_id * 2`;
• Always make the id of right child as `parent_id * 2 + 1`;

So we can just:

1. Record the `id` of `left most node` when first time at each level of the tree during an pre-order run.(you can tell by check the size of the container to hold the first nodes);
2. At each node, compare the `distance` from it the left most node with the current `max width`;

DFS - Return Value
C++

``````class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
vector<int> lefts; // left most nodes at each level;
return dfs(root, 1, 0, lefts);
}
private:
int dfs(TreeNode* n, int id, int d, vector<int>& lefts) { // d : depth
if (!n) return 0;
if (d >= lefts.size()) lefts.push_back(id);  // add left most node
return max({id + 1 - lefts[d], dfs(n->left, id * 2, d + 1, lefts), dfs(n->right, id * 2 + 1, d + 1, lefts)});
}
};
``````

3 liner

``````class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
unordered_map<int, vector<int>> m;
function<int(TreeNode*, int, int)> dfs = [&](TreeNode* n, int id, int d){ return n ? m[d].push_back(id), max({id+1-m[d][0], dfs(n->left, id*2, d+1), dfs(n->right, id*2+1, d+1)}) : 0; };
return dfs(root, 1, 0);
}
};
``````

Java

``````class Solution {
public int widthOfBinaryTree(TreeNode root) {
List<Integer> lefts = new ArrayList<Integer>(); // left most nodes at each level;
return dfs(root, 1, 0, lefts);
}

private int dfs(TreeNode n, int id, int d, List<Integer> lefts) { // d : depth
if (n == null) return 0;
if (d >= lefts.size()) lefts.add(id);   // add left most node
return Math.max(id + 1 - lefts.get(d), Math.max(dfs(n.left, id*2, d+1, lefts), dfs(n.right, id*2+1, d+1, lefts)));
}
}
``````

DFS - Side Effect
C++

``````class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
vector<int> lefts; // left most nodes at each level;
int maxwidth = 0;
dfs(root, 1, 0, lefts, maxwidth);
return maxwidth;
}
private:
void dfs(TreeNode* node, int id, int depth, vector<int>& lefts, int& maxwidth) {
if (!node) return;
if (depth >= lefts.size()) lefts.push_back(id);  // add left most node
maxwidth = max(maxwidth, id + 1 - lefts[depth]);
dfs(node->left, id * 2, depth + 1, lefts, maxwidth);
dfs(node->right, id * 2 + 1, depth + 1, lefts, maxwidth);
}
};
``````

Java

``````class Solution {
public int widthOfBinaryTree(TreeNode root) {
List<Integer> lefts = new ArrayList<Integer>(); // left most nodes at each level;
int[] res = new int[1]; // max width
dfs(root, 1, 0, lefts, res);
return res[0];
}
private void dfs(TreeNode node, int id, int depth, List<Integer> lefts, int[] res) {
if (node == null) return;
if (depth >= lefts.size()) lefts.add(id);   // add left most node
res[0] = Integer.max(res[0], id + 1 - lefts.get(depth));
dfs(node.left,  id * 2,     depth + 1, lefts, res);
dfs(node.right, id * 2 + 1, depth + 1, lefts, res);
}
}
``````

BFS
C++

``````class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (!root) return 0;
int max = 0;
queue<pair<TreeNode*, int>> q;
q.push(pair<TreeNode*, int>(root, 1));
while (!q.empty()) {
int l = q.front().second, r = l; // right started same as left
for (int i = 0, n = q.size(); i < n; i++) {
TreeNode* node = q.front().first;
r = q.front().second;
q.pop();
if (node->left) q.push(pair<TreeNode*, int>(node->left, r * 2));
if (node->right) q.push(pair<TreeNode*, int>(node->right, r * 2 + 1));
}
max = std::max(max, r + 1 - l);
}
return max;
}
};
``````

Java

``````import java.util.AbstractMap;
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
int max = 0;
Queue<Map.Entry<TreeNode, Integer>> q = new LinkedList<Map.Entry<TreeNode, Integer>>();
q.offer(new AbstractMap.SimpleEntry(root, 1));

while (!q.isEmpty()) {
int l = q.peek().getValue(), r = l; // right started same as left
for (int i = 0, n = q.size(); i < n; i++) {
TreeNode node = q.peek().getKey();
r = q.poll().getValue();
if (node.left != null) q.offer(new AbstractMap.SimpleEntry(node.left, r * 2));
if (node.right != null) q.offer(new AbstractMap.SimpleEntry(node.right, r * 2 + 1));
}
max = Math.max(max, r + 1 - l);
}

return maxwidth;
}
}
``````

• @alexander Thank you for your answer. I had a quick question. As per my understanding, the question does not mention that the tree is always rooted at `1`. During the contest, what made you think that it will always be rooted at `1` (and consequently think about the above approach)?

• @BatCoder
Because zero does not work : 2*0 == 0 which means left child will override parent. As he has pointed out briefly, this array indexing is generally been seen in priority queue, e.g. max/min heap which is used for example in heap-sort. See here for example: http://www.always-a-programmer.com/blog/sort/#section-heap-sort

• Is it faster to use an array to record the current maximum width?

• @captainjtx Sorry, let me rephrase my question. Why isn't it assumed that the root node can start at number, like say, `5`? The value of `id` has been hard-coded by @alexander to be `1`; what is the intuition behind starting with `1` and not something like `5`?

• @BatCoder
Okay, if you use other number n other than 1. The left child of root would be 2n-1 and right child would be 2n+1. The width of the second depth would be (2n+1-2n-1) = n+1. You can see only n=1 makes sense. Like I said, this indexing is initially seen in the array representation of binary tree, especially max/min heap. You may wanna take a closer look at the binary tree @alexander draw. The numbers he put in the tree can actually be seen as index to a one-based array. It's like this, root is the first element in the array. Left child is the second element right child is the third element and so on. For a complete binary tree, it is not difficult to prove that for any node, it is left child can be indexed as 2n-1 and right child can be indexed as 2n+1. Hope you find it useful

• This post is deleted!

• There is a test case where tree only has right nodes. In that case the index of the node will overflow.
Luckily, that case is passed in this code. I think there is a testcase possible for which this code might fail.

• @arjunjajoo In that case, you can submit a testcase so that the admin would add it. In order to do this, you need to hit the `Contribute` button near the text box wherein the test cases are displayed (below the editor). Thanks!

• Give each binary tree node a index, just like `heap`:

``````          root: i
left:i * 2   right: i * 2 + 1
``````

`List<Integer> lefts` records the left-most index of one level.
Compare all nodes distance to its level left-most node.

``````    int max = 0;
public int widthOfBinaryTree(TreeNode root) {
helper(root, new ArrayList<Integer>(), 0, 0);
return max;
}

void helper(TreeNode root, List<Integer> lefts, int level, int index){
if(root == null) return;
if(level == lefts.size()){