Maximum Width of Binary Tree

class Solution {
    private Integer maximumWidth = 0;
    private HashMap<Integer, Integer> levelMinColIndex;

    protected void traverse(TreeNode node, Integer level, Integer columnIndex) {
        if (node == null)
            return;
        if (!levelMinColIndex.containsKey(level)) {
            levelMinColIndex.put(level, columnIndex);
        }
        Integer minIndex = levelMinColIndex.get(level);

        maximumWidth = Math.max(maximumWidth, columnIndex - minIndex + 1);

        traverse(node.left, level + 1, 2 * columnIndex);
        traverse(node.right, level + 1, 2 * columnIndex + 1);
    }

    public int widthOfBinaryTree(TreeNode root) {
        this.levelMinColIndex = new HashMap<Integer, Integer>();
        traverse(root, 0, 0);
        return this.maximumWidth;
    }
}

The provided Java code calculates the maximum width of a binary tree, with the width defined as the number of nodes spanning the maximum horizontal distance between the leftmost and rightmost nodes at any level of the tree. It employs a depth-first search (DFS) traversal approach, utilizing recursion.

Here's the breakdown of how the code operates:

• A private member variable named maximumWidth stores the maximum width found during the traversal.
• A HashMap named levelMinColIndex keeps track of the minimum column index observed for each level, facilitating width calculation by mapping each level to its leftmost node's index.

The traverse method, which performs the recursive DFS, operates as follows:

• The method terminates if it encounters a null node, effectively handling leaf node children.
• It checks if the current level is already recorded in levelMinColIndex. If not, it inserts the current node's column index as the starting index for that level.
• It calculates the width for the level by computing the difference between the current node's column index and the minimum index stored in levelMinColIndex for that level, updating maximumWidth if the current width exceeds previously recorded values.

The traversal logic is recursive:

• For the left child node, the column index is set to 2 * columnIndex.
• For the right child node, it is 2 * columnIndex + 1, effectively simulating the binary tree structure's breadth expansion in a linear data structure like an array.

The widthOfBinaryTree method initializes the necessary structures and kicks off the traversal starting from the root node at column index 0 and level 0.

Upon completion of the traversal, widthOfBinaryTree returns the calculated maximumWidth, representing the result for the maximum width of the given binary tree.

This algorithm is efficient in terms of both time and space since it only processes each node once and uses a hashmap to dynamically store the minimum indices per level.

class Solution:
    def maxWidthOfTree(self, root: TreeNode) -> int:
        
        # Dictionary to keep track of the first column index at each tree level
        level_start_indices = {}
        width_max = 0

        def traverse_tree(node, lvl, idx):
            nonlocal width_max
            if node is None:
                return
            
            # Store first column index if it's missing for the level
            if lvl not in level_start_indices:
                level_start_indices[lvl] = idx

            # Update the max width using the level's first column index
            width_max = max(width_max, idx - level_start_indices[lvl] + 1)

            # Depth-first search: Left then Right
            traverse_tree(node.left, lvl + 1, 2 * idx)
            traverse_tree(node.right, lvl + 1, 2 * idx + 1)

        traverse_tree(root, 0, 0)

        return width_max

The code provided solves the problem of finding the maximum width of a binary tree using Python. The method maxWidthOfTree in the Solution class is implemented to determine this width, where the width is defined as the maximum number of nodes at any level of the tree.

• Initiate a dictionary level_start_indices to track the column index of the first node at each level of the tree.
• Start with a width_max variable set to 0 to track the maximum width encountered.
• Define a recursive function traverse_tree that traverses the tree nodes using Depth First Search (DFS). This internal function takes the current node, its level (lvl), and column index (idx) as arguments:
  • Returns immediately if the current node is None.
  • Records the column index of the first node at each level in level_start_indices if not already set.
  • Updates width_max by comparing it with the current width at that level which is calculated using column indices.
  • Calls itself to process the left child node with updated level and column index.
  • Calls itself to process the right child node with updated level and column index.
• Kickstarts the traversal from the root node at level 0 and index 0.
• Returns width_max which holds the maximum width of the tree.

Use this method to measure the maximum width of a binary tree effectively, ensuring efficient handling with depth-first traversal and careful index management.