662. Maximum Width of Binary 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.
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.
What are the most two important steps in writing a depth first search function? (Select 2)
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 position1in a hypothetical complete binary tree. -
Level-wise Traversal: A
whileloop 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 adding1(to include the first node in the count). The calculationans = 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 to2*i), and if it has a right child, the right child is given an indexi << 1 | 1(equivalent to2*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.
What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
Example Walkthrough
Let's consider a binary tree for our example:
1 1 2 / \ 3 3 2 4 / \ 55 9
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 indexed1. 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
whileloop. -
Finding Width: For this level, which is just the root, the width will be
q[-1][1] - q[0][1] + 1, meaning1 - 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
3is given index2*1 = 2, and node2is given index2*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 widthans = max(1, 2) = 2. -
Index Assignment & Queue Updates for Second Level: Node
5gets an index2*2 = 4, and node9gets an index2*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 updateans = 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
391import 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}
571#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};
511// 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.
57Which data structure is used to implement priority queue?
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.
What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.