Maximum Width of BT

Binary Trees FAQs Medium

This programming problem, essentially about finding the maximum width of a binary tree, has direct applications in creating balanced search algorithms in databases
Database management systems often use tree data structures (B-trees, B+ trees, etc
) to ensure faster access to information
The width here represents the number of nodes in each level of the tree, and keeping this number balanced or controlled allows databases to ensure efficient querying times
This problem reinforces the importance of understanding and handling tree data structures effectively, as this can directly influence the performance of many software applications that depend on databases

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels. The width of a level is determined by measuring the distance between its end nodes, which are the leftmost and rightmost non-null nodes. The length calculation additionally takes into account the null nodes that would be present between the end nodes if a full binary tree were to stretch down to that level.

Examples:

Input : root = [1, 3, 2, 5, 3, null, 9]

Output : 4

Explanation :

Input : root = [1, 3, 2, 5, null, null, 9, 6, null, 7]

Output : 7

Explanation :

Input : root = [5, 1, 2, 8, null, 4, 5, null, 6]

Constraints

1 <= Number of Nodes <= 3000
-1000 <= Node.val <= 1000

Hints

Initialize a queue with (root, index = 0), where index represents the position in a complete binary tree. Perform BFS level by level
Track the first and last index of nodes at the current level. Compute width as last_index - first_index + 1 and update max_width. Add children to the queue with calculated indices based on complete tree properties

Company Tags

Ubisoft Salesforce OYO Rooms Electronic Arts Airbnb Medtronic American Express Reddit Cloudflare Stripe Intel ARM Riot Games Epic Games Broadcom Oracle Unity Technologies Swiggy Optum Instacart Freshworks Bloomberg Zynga Byju's Shopify Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

Intuition

The objective is to determine the maximum width of a binary tree, which is defined as the widest level of the tree in terms of node count. To achieve this, we track the leftmost and rightmost node indices at each level. By calculating the width at each level using these indices, we can ascertain the maximum width of the tree. The approach involves assigning an index to the root node and then using level-order traversal to explore the tree. The index of each child node is derived from its parent node's index, which facilitates the calculation of widths at each level. This method ensures a systematic and efficient evaluation of the tree's width, ultimately identifying the maximum width observed throughout the traversal.

Approach

Begin by initializing a variable ans to keep track of the maximum width encountered. If the root node is null, return 0 as the width of an empty tree is zero.
Set up a queue for level-order traversal, where each queue element is a pair consisting of a node and its index within the level. Start by enqueuing the root node along with its initial index of 0.
While the queue contains elements, process each level as follows:
- Determine the number of nodes at the current level by measuring the size of the queue. Capture the index of the first node in the level to establish the leftmost position at that level.
- Initialize variables first and last to record the indices of the first and last nodes at the current level.
- For each node in the current level, compute its relative position based on the level's minimum index. Update the first and last variables to reflect the indices of the first and last nodes in this level. Enqueue the left and right children of the current node, assigning them indices of 2 x current index and 2 x current index + 1, respectively.
After processing all nodes in the level, update the maximum width ans by calculating the difference between last and first, and adding 1.
Continue the level-order traversal until all levels are examined. The final value of ans represents the maximum width of the binary tree, which is then returned.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function widthOfBinaryTree to find the 
    // maximum width of the Binary Tree
    int widthOfBinaryTree(TreeNode* root) {
        // If the root is null,
        // the width is zero
        if (!root) {
            return 0;
        }

        // Initialize a variable 'ans'
        // to store the maximum width
        int ans = 0;

        // Create a queue to perform level-order
        // traversal, where each element is a pair
        // of TreeNode* and its position in the level
        queue<pair<TreeNode*, int>> q;
        // Push the root node and its
        // position (0) into the queue
        q.push({root, 0});

        // Perform level-order traversal
        while (!q.empty()) {
            // Get the number of
            // nodes at the current level
            int size = q.size();
            // Get the position of the front
            // node in the current level
            int mmin = q.front().second;
            
            // Store the first and last positions 
            // of nodes in the current level
            int first = 0, last = 0;

            // Process each node
            // in the current level
            for (int i = 0; i < size; i++) {
                // Calculate current position relative
                // to the minimum position in the level
                int cur_id = q.front().second - mmin;
                // Get the current node
                TreeNode* node = q.front().first;
                // Pop the front node from the queue
                q.pop();

                // If this is the first node in the level, 
                // update the 'first' variable
                if (i == 0) {
                    first = cur_id;
                }

                // If this is the last node in the level,
                // update the 'last' variable
                if (i == size - 1) {
                    last = cur_id;
                }

                // Enqueue the left child of the 
                // current node with its position
                if (node->left) {
                    q.push({node->left, cur_id * 2 + 1});
                }

                // Enqueue the right child of the
                // current node with its position
                if (node->right) {
                    q.push({node->right, cur_id * 2 + 2});
                }
            }

            // Update the maximum width by calculating
            // the difference between the first and last
            // positions, and adding 1
            ans = max(ans, last - first + 1);
        }

        // Return the maximum
        // width of the binary tree
        return ans;
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(5);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(2);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(8);
    root->left->right->left = new TreeNode(7);
    root->left->right->right = new TreeNode(4);

    Solution sol;

    int maxWidth = sol.widthOfBinaryTree(root);

    cout << "Maximum width of the binary tree is: " << maxWidth << endl;

    return 0;
}
import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int data;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { data = val; left = null, right = null; }
 * }
 **/

class Solution {
    // Function widthOfBinaryTree to find the 
    // maximum width of the Binary Tree
    public int widthOfBinaryTree(TreeNode root) {
        // If the root is null,
        // the width is zero
        if (root == null) {
            return 0;
        }

        // Initialize a variable 'ans'
        // to store the maximum width
        int ans = 0;

        // Create a queue to perform level-order
        // traversal, where each element is a pair
        // of TreeNode* and its position in the level
        Queue<Pair<TreeNode, Integer>> q = new LinkedList<>();
        // Push the root node and its
        // position (0) into the queue
        q.offer(new Pair<>(root, 0));

        // Perform level-order traversal
        while (!q.isEmpty()) {
            // Get the number of
            // nodes at the current level
            int size = q.size();
            // Get the position of the front
            // node in the current level
            int mmin = q.peek().getValue();
            
            // Store the first and last positions 
            // of nodes in the current level
            int first = 0, last = 0;

            // Process each node
            // in the current level
            for (int i = 0; i < size; i++) {
                // Calculate current position relative
                // to the minimum position in the level
                int cur_id = q.peek().getValue() - mmin;
                // Get the current node
                TreeNode node = q.peek().getKey();
                // Pop the front node from the queue
                q.poll();

                // If this is the first node in the level, 
                // update the 'first' variable
                if (i == 0) {
                    first = cur_id;
                }

                // If this is the last node in the level,
                // update the 'last' variable
                if (i == size - 1) {
                    last = cur_id;
                }

                // Enqueue the left child of the 
                // current node with its position
                if (node.left != null) {
                    q.offer(new Pair<>(node.left, cur_id * 2 + 1));
                }

                // Enqueue the right child of the
                // current node with its position
                if (node.right != null) {
                    q.offer(new Pair<>(node.right, cur_id * 2 + 2));
                }
            }

            // Update the maximum width by calculating
            // the difference between the first and last
            // positions, and adding 1
            ans = Math.max(ans, last - first + 1);
        }

        // Return the maximum
        // width of the binary tree
        return ans;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        Solution sol = new Solution();
        int maxWidth = sol.widthOfBinaryTree(root);

        System.out.println("Maximum width of the binary tree is: " + maxWidth);
    }
}
from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    # Function widthOfBinaryTree to find the 
    # maximum width of the Binary Tree
    def widthOfBinaryTree(self, root):
        # If the root is null,
        # the width is zero
        if not root:
            return 0

        # Initialize a variable 'ans'
        # to store the maximum width
        ans = 0

        # Create a queue to perform level-order
        # traversal, where each element is a pair
        # of TreeNode* and its position in the level
        q = deque([(root, 0)])

        # Perform level-order traversal
        while q:
            # Get the number of
            # nodes at the current level
            size = len(q)
            # Get the position of the front
            # node in the current level
            mmin = q[0][1]

            # Store the first and last positions 
            # of nodes in the current level
            first = last = 0

            # Process each node
            # in the current level
            for i in range(size):
                # Calculate current position relative
                # to the minimum position in the level
                cur_id = q[0][1] - mmin
                # Get the current node
                node = q[0][0]
                # Pop the front node from the queue
                q.popleft()

                # If this is the first node in the level, 
                # update the 'first' variable
                if i == 0:
                    first = cur_id

                # If this is the last node in the level,
                # update the 'last' variable
                if i == size - 1:
                    last = cur_id

                # Enqueue the left child of the 
                # current node with its position
                if node.left:
                    q.append((node.left, cur_id * 2 + 1))

                # Enqueue the right child of the
                # current node with its position
                if node.right:
                    q.append((node.right, cur_id * 2 + 2))

            # Update the maximum width by calculating
            # the difference between the first and last
            # positions, and adding 1
            ans = max(ans, last - first + 1)

        # Return the maximum
        # width of the binary tree
        return ans


if __name__ == "__main__":
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)
    root.left.right.left = TreeNode(7)
    root.left.right.right = TreeNode(4)

    sol = Solution()
    maxWidth = sol.widthOfBinaryTree(root)

    print("Maximum width of the binary tree is:", maxWidth)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *      constructor(val = 0, left = null, right = null){
 *          this.data = val;
 *          this.left = left;
 *          this.right = right;
 *      }
 * }
 **/

class Solution {
    // Function widthOfBinaryTree to find the 
    // maximum width of the Binary Tree
    widthOfBinaryTree(root) {
        // If the root is null,
        // the width is zero
        if (!root) {
            return 0;
        }

        // Initialize a variable 'ans'
        // to store the maximum width
        let ans = 0;

        // Create a queue to perform level-order
        // traversal, where each element is a pair
        // of TreeNode* and its position in the level
        let q = [[root, 0]];

        // Perform level-order traversal
        while (q.length > 0) {
            // Get the number of
            // nodes at the current level
            let size = q.length;
            // Get the position of the front
            // node in the current level
            let mmin = q[0][1];
            
            // Store the first and last positions 
            // of nodes in the current level
            let first, last;

            // Process each node
            // in the current level
            for (let i = 0; i < size; i++) {
                // Calculate current position relative
                // to the minimum position in the level
                let cur_id = q[0][1] - mmin;
                // Get the current node
                let node = q[0][0];
                // Pop the front node from the queue
                q.shift();

                // If this is the first node in the level, 
                // update the 'first' variable
                if (i == 0) {
                    first = cur_id;
                }

                // If this is the last node in the level,
                // update the 'last' variable
                if (i == size - 1) {
                    last = cur_id;
                }

                // Enqueue the left child of the 
                // current node with its position
                if (node.left) {
                    q.push([node.left, cur_id * 2 + 1]);
                }

                // Enqueue the right child of the
                // current node with its position
                if (node.right) {
                    q.push([node.right, cur_id * 2 + 2]);
                }
            }

            // Update the maximum width by calculating
            // the difference between the first and last
            // positions, and adding 1
            ans = Math.max(ans, last - first + 1);
        }

        // Return the maximum
        // width of the binary tree
        return ans;
    }
}

// Example usage
let root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

let sol = new Solution();
let maxWidth = sol.widthOfBinaryTree(root);

console.log("Maximum width of the binary tree is: " + maxWidth);

Complexity Analysis

Time Complexity: O(N) where N is the number of nodes in the binary tree. Each node of the binary tree is enqueued and dequeued exactly once, hence all nodes need to be processed and visited. Processing each node takes constant time operations which contributes to the overall linear time complexity.

Space Complexity: O(N) where N is the number of nodes in the binary tree. In the worst case, the queue has to hold all the nodes of the last level of the binary tree, the last level could at most hold N/2 nodes hence the space complexity of the queue is proportional to O(N).

Code

Problem List