Approach Framework
Explanation
As we need to reach every node in the given tree, we will have to traverse the tree, either with a depthfirst search, or with a breadthfirst search.
The main idea in this question is to give each node a position
value. If we go down the left neighbor, then position > position * 2
; and if we go down the right neighbor, then position > position * 2 + 1
. This makes it so that when we look at the position values L
and R
of two nodes with the same depth, the width will be R  L + 1
.
Approach #1: BreadthFirst Search [Accepted]
Intuition and Algorithm
Traverse each node in breadthfirst order, keeping track of that node's position. For each depth, the first node reached is the leftmost, while the last node reached is the rightmost.
Complexity Analysis

Time Complexity: where is the number of nodes in the input tree. We traverse every node.

Space Complexity: , the size of our
queue
.
Approach #2: DepthFirst Search [Accepted]
Intuition and Algorithm
Traverse each node in depthfirst order, keeping track of that node's position. For each depth, the position of the first node reached of that depth will be kept in left[depth]
.
Then, for each node, a candidate width is pos  left[depth] + 1
. We take the maximum of the candidate answers.
Complexity Analysis

Time Complexity: where is the number of nodes in the input tree. We traverse every node.

Space Complexity: , the size of the implicit call stack in our DFS.
Analysis written by: @awice.