662. Maximum Width of Binary Tree

MediumTreeDepth-First SearchBreadth-First SearchBinary Tree

Problem Description

The problem presents a binary tree and requires finding the maximum width of the tree. The maximum width refers to the largest number of nodes between the leftmost and rightmost non-null nodes across all levels of the tree, including the null nodes that would be present if the tree were a complete binary tree down to that level.

Imagine looking at each level of the binary tree and stretching a rubber band from the first (leftmost) to the last (rightmost) node that exists at that level, specifying to also include the places where a node would be if the tree were complete. The width is the length of this rubber band, and our task is to find the longest one.

The problem guarantees that the maximum width can be stored within a 32-bit signed integer, which specifies an upper limit to the size of our answer.

Flowchart Walkthrough

Let's analyze the problem using the Flowchart. Here's a step-by-step approach for leetcode 662. Maximum Width of Binary Tree, determining the appropriate algorithm:

Is it a graph?

Yes: A binary tree can be considered a graph where each node has edges connecting it to its children.

Is it a tree?

Yes: Specifically, the structure described is a binary tree, which is a type of tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: While a tree is a directed acyclic graph, the classification in the flowchart leads directly from "tree" to using a DFS technique for tree-related problems without needing to go through the DAG node.

Is the problem related to shortest paths?

No: We are measuring the width at different levels, not searching for shortest paths.

Does the problem involve connectivity?

No: This isn't about connectivity between nodes across separate components, but rather about measuring elements within the structure of the tree.

Conclusion: Following the flowchart, since we are dealing with a tree and none of the other conditions (like DAG, shortest paths, or connectivity concerns) complicate the task, the suggested algorithm is to use DFS specifically adapted for calculating maximum widths at tree levels.

Intuition

To solve this problem, we can use either Breadth-First Search (BFS) or Depth-First Search (DFS). The solution provided here uses BFS, which is often a natural choice for problems involving levels of a tree.

The intuition behind using BFS is that we process nodes level by level. At each level, we can measure the width by keeping track of the position of each node. We can assign an index to each node as if it were in a complete binary tree. This is done by numbering the root as 1, the left child as 2i, and the right child as 2i+1 (where i is the index of the current node).

We utilize a queue to keep track of nodes along with their indices. For each level, we calculate the width as the difference between the indices of the first and last nodes in the queue plus 1 (to account for the first node). We then update our answer to be the maximum width found so far.

Note that these indices can become very large since they double at each level, but we are only interested in the width (the difference between indices), not the indices themselves. Thus, we can maintain relative indices at each level to avoid overflow issues and still correctly calculate the width.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The problem is solved using a breadth-first search (BFS), which is a common algorithm for traversing or searching tree or graph data structures. This approach works level by level, visiting all the nodes at the current depth before moving to the next.

Here is how the BFS solution is implemented:

Queue Initialization: A queue data structure is used to keep track of the nodes along with their indices. The queue is initialized by adding the root node with an index of 1. This index assumes that the root node is at position 1 in a hypothetical complete binary tree.
Level-wise Traversal: A while loop is used to iterate over the tree level by level as long as the queue is not empty.
Finding Width: At the start of each level, the current width is calculated by subtracting the index of the first node in the queue (q[0][1]) from the index of the last node in the queue (q[-1][1]) and adding 1 (to include the first node in the count). The calculation ans = max(ans, q[-1][1] - q[0][1] + 1) updates the maximum width found so far.
Index Assignment: Inside the loop, another loop iterates over the nodes present at the current level (determined by the current size of the queue). For each node, if it has a left child, the left child is given an index i << 1 (equivalent to 2*i), and if it has a right child, the right child is given an index i << 1 | 1 (equivalent to 2*i+1), aligning with the indexing for a complete binary tree.
Queue Updates: After calculating the width and assigning new indices, nodes are dequeued (popleft), and their children are enqueued with their respective calculated indices.
Returning the Result: Once the BFS traversal is complete, and the queue is emptied, the algorithm returns ans, the maximum width found across all levels of the input binary tree.

Throughout the BFS, deque from the Python collections module is used as an efficient queue implementation allowing constant time complexity for adding and removing nodes. Also, the tree nodes are presumed to be defined as a class with attributes val, left, and right. The solution handles tree nodes containing integer values and may have left and right children.

The bit manipulation used to assign indices (i << 1 and i << 1 | 1) is a performance optimization, as bit shifts are generally faster than multiplication or addition. This logic also ensures correctness when assigning positions to child nodes while keeping track of the overall structure for the width computation.

By structuring the BFS to consider indices as if they are part of a complete binary tree, the maximum width can be determined even if the actual tree is not complete, accounting for the non-null nodes and the gaps between them.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a binary tree for our example:

We will apply the BFS approach as described in the solution approach to find the maximum width of this tree.

Queue Initialization: We start by initializing a queue with the root node (1) and its index. The root is indexed 1. So the queue will have one element: [(1, 1)].
Level-wise Traversal: Now, we begin the level-by-level traversal. The queue is not empty, so we enter the while loop.
Finding Width: For this level, which is just the root, the width will be q[-1][1] - q[0][1] + 1, meaning 1 - 1 + 1 = 1. This is now our current maximum width, ans = 1.
Index Assignment: There are no other nodes at this level, so we move to the children. Node 3 is given index 2*1 = 2, and node 2 is given index 2*1+1 = 3.
Queue Updates: We remove the root node from the queue and add its children with their indexes, so the queue now has [(3, 2), (2, 3)].
Traverse Second Level: Now we process the second level. The width at this level would be 3 - 2 + 1 = 2. We update our maximum width ans = max(1, 2) = 2.
Index Assignment & Queue Updates for Second Level: Node 5 gets an index 2*2 = 4, and node 9 gets an index 2*3+1 = 7. Our queue is updated to contain [(5, 4), (9, 7)].
Traverse Third Level: At this level, we calculate the width using the indexes in the queue, 7 - 4 + 1 = 4. We update ans = max(2, 4) = 4.

Since nodes 5 and 9 do not have children, the loop ends, as the queue is now empty.

Returning the Result: The maximum width found during traversal is 4, which is the final answer for the maximum width of our example binary tree.

With this process, we have measured the maximum width of each level of the example tree and kept track of the largest value found, which is our answer to the problem. The width of the tree is the length of the longest rubber band we could stretch across any level, including both present and 'imaginary' (null) nodes, and for our example tree, that width is 4.

Solution Implementation

1from collections import deque
2
3# Definition for a binary tree node.
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10class Solution:
11    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
12        # Initialize the answer to zero, which will hold the maximum width
13        max_width = 0
14      
15        # Queue will hold tuples of tree node and its index in the tree
16        queue = deque([(root, 1)])
17      
18        # Continue the loop until the queue is empty
19        while queue:
20            # Calculate the current width using the first and last node's indices
21            current_width = queue[-1][1] - queue[0][1] + 1
22            max_width = max(max_width, current_width)  # Update maximum width
23          
24            # Iterate over the current level of the tree
25            for _ in range(len(queue)):
26                # Pop the node and its index from the queue
27                node, index = queue.popleft()
28              
29                # If the left child exists, add it to the queue
30                if node.left:
31                    queue.append((node.left, index << 1))
32                  
33                # If the right child exists, add it to the queue
34                if node.right:
35                    queue.append((node.right, (index << 1) | 1))
36      
37        # Return the maximum width found
38        return max_width
39

1import javafx.util.Pair; // Ensure Pair class is imported, JavaFX or Apache Commons Lang (or define your own Pair class if needed)
2
3/**
4 * Definition for a binary tree node.
5 */
6class TreeNode {
7    int val;
8    TreeNode left;
9    TreeNode right;
10    TreeNode() {}
11    TreeNode(int val) { this.val = val; }
12    TreeNode(int val, TreeNode left, TreeNode right) {
13        this.val = val;
14        this.left = left;
15        this.right = right;
16    }
17}
18
19class Solution {
20    public int widthOfBinaryTree(TreeNode root) {
21        // Queue to hold nodes and their respective indices in the tree
22        Deque<Pair<TreeNode, Integer>> queue = new ArrayDeque<>();
23        // Start with the root node and index 1
24        queue.offer(new Pair<>(root, 1));
25        // Initialize the maximum width
26        int maxWidth = 0;
27      
28        // Loop until there are no more nodes to process
29        while (!queue.isEmpty()) {
30            // Calculate the width of the current level
31            // The width is the difference in indices between the first and last nodes + 1
32            maxWidth = Math.max(maxWidth,
33                                queue.peekLast().getValue() - queue.peekFirst().getValue() + 1);
34          
35            // Iterate over all nodes at the current level
36            int levelSize = queue.size();
37            for (int i = 0; i < levelSize; ++i) {
38                // Poll the current node and its index
39                Pair<TreeNode, Integer> current = queue.pollFirst();
40                TreeNode currentNode = current.getKey();
41                int index = current.getValue();
42              
43                // Offer left child to queue if it exists
44                if (currentNode.left != null) {
45                    queue.offer(new Pair<>(currentNode.left, 2 * index));
46                }
47                // Offer right child to queue if it exists
48                if (currentNode.right != null) {
49                    queue.offer(new Pair<>(currentNode.right, 2 * index + 1));
50                }
51            }
52        }
53        // Return the maximum width found
54        return maxWidth;
55    }
56}
57

1#include <queue>
2#include <algorithm>
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode() : val(0), left(nullptr), right(nullptr) {}
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    int widthOfBinaryTree(TreeNode* root) {
17        if (!root) return 0; // Guard clause for an empty tree
18
19        std::queue<std::pair<TreeNode*, unsigned long>> queue; // Queue to perform level order traversal, holding nodes and their positions
20        queue.push({root, 1}); // Initialize with the root node with position 1
21        int maxWidth = 0; // Variable to store the maximum width found
22
23        while (!queue.empty()) {
24            int levelSize = queue.size(); // Number of nodes at the current level
25            unsigned long leftMost = queue.front().second; // Position of the leftmost node at the current level, used as an offset
26            unsigned long rightMost = queue.back().second; // Position of the rightmost node at the current level, used to calculate width
27            maxWidth = std::max(maxWidth, static_cast<int>(rightMost - leftMost) + 1); // Update maxWidth if necessary
28
29            // Iterate through the nodes of the current level
30            for (int i = 0; i < levelSize; ++i) {
31                auto nodePair = queue.front();
32                queue.pop();
33                TreeNode* currentNode = nodePair.first;
34                unsigned long position = nodePair.second;
35
36                // Subtract leftMost to avoid high values and overflow due to increasing node positions
37                position -= leftMost;
38
39                // Add children to the queue with their respective positions
40                if (currentNode->left) {
41                    queue.push({currentNode->left, 2 * position}); // Left child position
42                }
43                if (currentNode->right) {
44                    queue.push({currentNode->right, 2 * position + 1}); // Right child position
45                }
46            }
47        }
48        return maxWidth; // Return the maximum width found
49    }
50};
51

1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14// Function to compute the width of a binary tree.
15function widthOfBinaryTree(root: TreeNode | null): number {
16    // If the tree is empty, return width 0.
17    if (!root) return 0;
18
19    // Queue for level order traversal, holding nodes and their positions.
20    const queue: Array<{ node: TreeNode; position: number }> = [];
21    queue.push({ node: root, position: 1 });
22    let maxWidth = 0; // Variable to store the maximum width.
23
24    // While there are nodes in the queue to process...
25    while (queue.length > 0) {
26        const levelSize = queue.length; // Number of nodes at the current level.
27        const leftMost = queue[0].position; // Position of the leftmost node at the current level (used as an offset).
28      
29        // Iterate through the nodes of the current level.
30        for (let i = 0; i < levelSize; i++) {
31            const { node: currentNode, position: currentPosition } = queue.shift()!;
32
33            // On the last iteration, update maxWidth using currentPosition as the rightMost position.
34            if (i === levelSize - 1) {
35                maxWidth = Math.max(maxWidth, currentPosition - leftMost + 1);
36            }
37
38            // Subtract leftMost to avoid high values and potential overflow.
39            const adjustedPosition = currentPosition - leftMost;
40
41            // Add children to the queue with their respective positions.
42            if (currentNode.left) {
43                queue.push({ node: currentNode.left, position: 2 * adjustedPosition });
44            }
45            if (currentNode.right) {
46                queue.push({ node: currentNode.right, position: 2 * adjustedPosition + 1 });
47            }
48        }
49    }
50
51    return maxWidth; // Return the calculated maximum width of the binary tree.
52}
53
54// Example usage:
55// const root = new TreeNode(1, new TreeNode(3, new TreeNode(5), new TreeNode(3)), new TreeNode(2, null, new TreeNode(9)));
56// console.log(widthOfBinaryTree(root)); // Outputs the width of the tree.
57

Time and Space Complexity

Time Complexity

The time complexity of the function is determined by how many times we visit each node in the binary tree. In this code, every node is visited exactly once during the breadth-first search, so the time complexity is O(N), where N is the number of nodes in the binary tree.

Space Complexity

The space complexity depends on the maximum size of the queue used to store nodes at any level of the tree. In the worst case, when the tree is a complete binary tree, the maximum width is reached at the last level, which would contain approximately N/2 nodes (half of the total number of nodes). Therefore, the space complexity is O(N) in the worst case.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know