Max width of binary tree

Maximum Width of Binary Tree - LeetCodeLeetCode

Solution 1. BFS with Node Indices: One solution is to perform a breadth-first search (BFS) of the tree, while keeping track of the indices of each node in the BFS order. At each level, we can calculate the width as the difference between the indices of the first and last non-null nodes. We can keep track of the maximum width seen so far and return it at the end. This solution has a time complexity of O(n) and a space complexity of O(n).

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

Solution 2. DFS with Hash Map: A third solution is to perform a depth-first search (DFS) of the tree, while keeping track of the minimum and maximum x-coordinates of nodes at each level using a hash map. Specifically, we can traverse the tree recursively, passing down the current level and the x-coordinate of the current node. At each node, we can update the minimum and maximum x-coordinates for the current level in the hash map. We can then recursively traverse the left and right subtrees, passing down the current level + 1 and the updated x-coordinates. After the traversal, we can iterate over the hash map and calculate the width at each level as the difference between the maximum and minimum x-coordinates. We can keep track of the maximum width seen so far and return it at the end. This solution has a time complexity of O(n) and a space complexity of O(h), where h is the height of the tree (i.e., the maximum depth of the tree).

class Solution {
   // Similar to level traverse with DFS
    public int widthOfBinaryTree(TreeNode root) {
        // Initialize a hash map to keep track of min and max x-coordinates at each level
        Map<Integer, Pair<Integer, Integer>> levelMap = new HashMap<>();
        
        // Call the recursive traversal function
        traverse(root, 0, 0, levelMap);
        
        // Iterate over the level map to calculate the maximum width
        int maxWidth = 0;
        for (int level : levelMap.keySet()) {
            Pair<Integer, Integer> minMaxPair = levelMap.get(level);
            int width = minMaxPair.getValue() - minMaxPair.getKey() + 1;
            maxWidth = Math.max(maxWidth, width);
        }
        
        return maxWidth;
    }
    
    // Define a helper function to traverse the tree recursively
    private void traverse(TreeNode node, int level, int x, Map<Integer, Pair<Integer, Integer>> levelMap) {
        if (node == null) {
            return;
        }
        
        // Update the min and max x-coordinates for the current level
        if (!levelMap.containsKey(level)) {
            levelMap.put(level, new Pair(x, x));
        } else {
            Pair<Integer, Integer> prevPair = levelMap.get(level);
            levelMap.put(level, new Pair(prevPair.getKey(), x));
        }
        
        // Recursively traverse the left and right subtrees
        traverse(node.left, level + 1, 2 * x, levelMap);
        traverse(node.right, level + 1, 2 * x + 1, levelMap);
    }
}