LeetCode 662: Maximum Width of Binary Tree Solution

Master LeetCode problem 662 (Maximum Width of Binary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

662. Maximum Width of Binary Tree

Medium

Tree Depth-First Search Breadth-First Search Binary Tree

Problem Explanation

Explanation:

To find the maximum width of a binary tree, we can perform a level order traversal. At each level, we keep track of the indices of nodes in that level. The width of the current level is the difference between the index of the rightmost node and the index of the leftmost node. We update the maximum width found so far as we traverse through each level.

Algorithm:

Perform a level order traversal of the binary tree.
Keep track of the index of each node as we traverse the tree.
At each level, calculate the width by finding the difference between the index of the rightmost node and the index of the leftmost node.
Update the maximum width found so far.
Return the maximum width at the end.

Time Complexity:

The time complexity of this solution is O(n) where n is the number of nodes in the binary tree. This is because we visit each node once during the level order traversal.

Space Complexity:

The space complexity is O(n) where n is the number of nodes in the binary tree. This is due to the space required for the queue used in the level order traversal.

Solution Code

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));
        int maxWidth = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            int left = queue.peek().getValue();
            int right = left;
            
            for (int i = 0; i < size; i++) {
                Pair<TreeNode, Integer> current = queue.poll();
                TreeNode node = current.getKey();
                right = current.getValue();
                
                if (node.left != null) {
                    queue.offer(new Pair<>(node.left, 2 * right));
                }
                if (node.right != null) {
                    queue.offer(new Pair<>(node.right, 2 * right + 1));
                }
            }
            
            maxWidth = Math.max(maxWidth, right - left + 1);
        }
        
        return maxWidth;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 662 (Maximum Width of Binary Tree)?

This page provides optimized solutions for LeetCode problem 662 (Maximum Width of Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 662 (Maximum Width of Binary Tree)?

The time complexity for LeetCode 662 (Maximum Width of Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 662 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 662 in Java, C++, or Python.

Back to LeetCode Solutions