Maximum Width Of Binary Tree

Solution For Maximum Width Of Binary Tree

Problem Statement:

Given a binary tree, write a function to get the maximum width of the given tree. The maximum width of a tree is defined as the maximum number of nodes in any level. If the tree is empty, return 0.

Example:

Input:

  1
/   \

3 2
/ \ \
5 3 9

Output: 4

Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Solution:

To find the maximum width of the binary tree, we need to traverse the tree level by level and count the number of nodes in each level. We can use a queue for the breadth-first search and a map to store the position of each node in the level.

Algorithm:

  1. Initialize a queue to store the nodes of the tree and a map to store the position of each node.

  2. Start the breadth-first traversal of the binary tree by adding the root to the queue.

  3. While the queue is not empty, process each level of the tree.

  4. For each node in the queue, add its left and right child to the queue and update their positions in the map.

  5. After processing the current level, update the maximum width with the difference between the leftmost and rightmost positions in the level.

  6. Repeat steps 3-5 until the queue is empty.

  7. Return the maximum width of the tree.

Pseudo Code:

function max_width_binary_tree(root: TreeNode) -> int:
if not root:
return 0

queue = [(root, 0)]
level_positions = {}
max_width = 0

while queue:
    level_len = len(queue)

    for i in range(level_len):
        node, pos = queue.pop(0)
        level_positions[pos] = node

        if node.left:
            queue.append((node.left, 2*pos))

        if node.right:
            queue.append((node.right, 2*pos+1))

    level_width = level_positions[max(level_positions)]-level_positions[min(level_positions)]+1
    max_width = max(max_width, level_width)
    level_positions.clear()

return max_width

Time Complexity:

The time complexity of this algorithm is O(n) as we need to traverse all the nodes of the binary tree.

Space Complexity:

The space complexity of this algorithm is O(n) as we need to store the nodes in the queue and the positions in the map.

Step by Step Implementation For Maximum Width Of Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if(root==null)
            return 0;
        Queue queue=new LinkedList<>();
        queue.add(root);
        int maxWidth=1;
        while(!queue.isEmpty()){
            int count=queue.size();
            maxWidth=Math.max(maxWidth,count);
            for(int i=0;i
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        # Base case
        if not root: 
            return 0
        
        # Initialize variables
        queue = [[root, 0]] # list of [node, position] pairs
        max_width = 1 # max width of tree
        
        # Perform breadth first search
        while queue:
            # Get the size of the current level
            size = len(queue)
            
            # Get the left and right most positions of the current level
            leftmost = queue[0][1]
            rightmost = queue[size - 1][1]
            
            # Update max width if necessary
            max_width = max(max_width, rightmost - leftmost + 1)
            
            # Iterate through current level
            for i in range(size):
                # Get node and position from queue
                node, position = queue.pop(0)
                
                # Add children to queue if they exist
                if node.left:
                    queue.append([node.left, 2 * position])
                if node.right:
                    queue.append([node.right, 2 * position + 1])
                    
        return max_width
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var widthOfBinaryTree = function(root) {
    // edge case - if the tree is empty, return 0
    if (!root) return 0;
    
    // create a queue to store the nodes at each level
    let queue = [];
    
    // push the root node into the queue
    queue.push(root);
    
    // create a variable to store the maximum width
    let maxWidth = 0;
    
    // while the queue is not empty
    while (queue.length) {
        // store the length of the queue in a variable
        let queueLength = queue.length;
        
        // if the queue length is greater than the maximum width, update the maximum width
        if (queueLength > maxWidth) {
            maxWidth = queueLength;
        }
        
        // iterate through the queue
        for (let i = 0; i < queueLength; i++) {
            // store the node at the front of the queue in a variable
            let node = queue.shift();
            
            // if the node has a left child, push it into the queue
            if (node.left) {
                queue.push(node.left);
            }
            
            // if the node has a right child, push it into the queue
            if (node.right) {
                queue.push(node.right);
            }
        }
    }
    
    // return the maximum width
    return maxWidth;
    
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        queue> q; 
        int maxWidth = 0;
        q.push({root, 1});
        while(!q.empty()){
            int count = q.size();
            int start = q.front().second, end = q.back().second;
            maxWidth = max(maxWidth, end-start+1);
            for(int i = 0; i < count; i++){
                TreeNode* curr = q.front().first;
                int idx = q.front().second;
                q.pop();
                if(curr->left) q.push({curr->left, 2*idx});
                if(curr->right) q.push({curr->right, 2*idx+1});
            }
        }
        return maxWidth;
    }
};
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int WidthOfBinaryTree(TreeNode root) {
        // Base case
        if (root == null) {
            return 0;
        }
        
        // Queue to store all the nodes at each level
        Queue queue = new Queue();
        
        // Variable to store the maximum width
        int maxWidth = 0;
        
        // Add the root node to the queue
        queue.Enqueue(root);
        
        // Loop through the queue while it's not empty
        while (queue.Count != 0) {
            // Get the size of the queue
            int size = queue.Count;
            
            // Update the maximum width
            maxWidth = Math.Max(maxWidth, size);
            
            // Loop through all the nodes in the queue
            for (int i = 0; i < size; i++) {
                // Get the node from the queue
                TreeNode node = queue.Dequeue();
                
                // Add the left child to the queue
                if (node.left != null) {
                    queue.Enqueue(node.left);
                }
                
                // Add the right child to the queue
                if (node.right != null) {
                    queue.Enqueue(node.right);
                }
            }
        }
        
        // Return the maximum width
        return maxWidth;
    }
}


Scroll to Top

Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]