Max width of a Binary Tree

Dec 18, 2024 • 5 mins read

Problem Overview

Problem Title: Maximum Width of Binary Tree

LeetCode URL: Maximum Width of Binary Tree

In this problem, the goal is to determine the maximum width of a binary tree. The width of one level is defined as the number of nodes present between the leftmost and rightmost non-null nodes inclusive. You are required to return the maximum width among all levels of the given binary tree.

Understanding the Problem

The task is to compute the maximum width of a binary tree, where width is counted as the number of nodes found at the widest level from leftmost to rightmost non-null node. This involves traversing the tree and tracking node positions at each level to determine the maximum span. Nodes may have null children, but these are not counted towards the width.

What is a Binary Tree?

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. Binary trees are used to implement binary search trees and heaps and are fundamental data structures in computer science.

Key DSA Concepts and Theory

Binary Tree Level Order Traversal

Binary tree level order traversal, also known as breadth-first traversal, processes nodes level by level. The most common method to achieve this is by using a queue. Each node is enqueued with its position index, which helps us calculate the width of each level.

Queue Data Structure

Queuing is essential as it allows nodes to be processed in the order they appear on each level. It facilitates the addition of each child node while maintaining the parent-child relationship across levels.

Calculating Width

For each depth level, we calculate the width using the index positions of nodes. The width is the difference between the last and first node's indices plus one.

Solution Approach

To solve the problem, a breadth-first search (BFS) approach using a queue is optimum. We'll make use of indices to track positions across the tree even as we keep track of null nodes by assigning indices that respect the binary property:

Initialization: Start BFS with a queue containing the root node and its position index (0).
Level Order Traversal:
- For each level:
  - Determine the number of nodes.
  - Record the indices of nodes encountered.
  - Compute the width of the current level using the first and last node indices.
- Enqueue children of current nodes with respective computed indices for the next level processing.
Result Evaluation: Maintain and update the maximum width encountered.

Here is the implementation in C++ and Java:

C++ Solution

#include <iostream>
#include <queue>
using namespace std;

// 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) {}
};

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    int maxWidth = 0;
    queue<pair<TreeNode*, unsigned long long>> q;
    q.push({root, 0});
    while (!q.empty()) {
        int size = q.size();
        unsigned long long start = q.front().second;
        unsigned long long end = q.back().second;
        maxWidth = max(maxWidth, int(end - start + 1));
        for (int i = 0; i < size; ++i) {
            auto [node, index] = q.front();
            q.pop();
            if (node->left) q.push({node->left, 2 * index});
            if (node->right) q.push({node->right, 2 * index + 1});
        }
    }
    return maxWidth;
}

Java Solution

import java.util.LinkedList;
import java.util.Queue;

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;
    }
}

public class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        int maxWidth = 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));
        while (!queue.isEmpty()) {
            int size = queue.size();
            int start = queue.peek().getValue();
            int end = queue.peek().getValue();
            for (int i = 0; i < size; i++) {
                Pair<TreeNode, Integer> p = queue.poll();
                TreeNode node = p.getKey();
                int index = p.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));
                end = index;
            }
            maxWidth = Math.max(maxWidth, end - start + 1);
        }
        return maxWidth;
    }
}

class Pair<K, V> {
    private K key;
    private V value;
    
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    
    public K getKey() { return key; }
    public V getValue() { return value; }
}

Time and Space Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the binary tree. The algorithm traverses each node exactly once.
Space Complexity: O(w), where w is the maximum width of the binary tree. In the worst-case scenario, the queue might contain all nodes at the widest level.

Common Mistakes to Avoid

Index Overflows: Ensure the indices are managed efficiently with the right data type to prevent overflow. In C++, unsigned long long is used for indices.
Left and Right Subtree Indexing: Always remember that the left child of a node at index i should be at index 2 * i, and the right child should be at 2 * i + 1.

Additional Resources and References

This comprehensive explanation and implementation of the "Maximum Width of Binary Tree" problem should help you understand the intricacies of binary tree manipulations necessary to solve this problem.

Terms & Conditions Privacy Policy Refund Policy