Home » leet code » Leet Code 662. maximum width of binary tree (Medium)

# Leet Code 662. maximum width of binary tree (Medium)

maximum width of binary tree :Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Maximum Width of Binary Tree” problem.

Binary Tree Level Order Traversal

## Method 1: Level Order Traversal using Queue

### Algorithm:

1. Initialize a queue and enqueue the root node.
2. While the queue is not empty:
a. Dequeue the front node and process it.
b. Enqueue its child nodes (if any).
3. Keep track of the maximum width encountered during traversal.

Note : Level oder Travesal is equivalent to BFS search .

Time Complexity: O(N) (Linear)

Space Complexity: O(w) (w = maximum width of the tree)

## Code

### C++ : Level Order maximum width of binary tree

``````class Solution {
static class pair{
TreeNode node;
int num;
pair(TreeNode node,int num){
this.node=node;
this.num=num;
}
}
public int widthOfBinaryTree(TreeNode root) {
int ans=0;
while(!q.isEmpty()){
int n=q.size();
int idx=q.peek().num;

int first=0;
int last=0;

for(int i=0;i<n;i++){
int curridx=q.peek().num-idx;
TreeNode node=q.peek().node;
q.poll();
if(i==0) first= curridx;
if(i==n-1)last=curridx;
if(node.left!=null){
}
if(node.right!=null){
}
}
ans=Math.max(last-first+1,ans);
}
return ans;
}
}
``````

Binary Trees – Data structure – Nilesh blog.tech

### Python: Level Order maximum width of binary tree

``````from collections import deque

class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
if not root:
return 0

class Pair:
def __init__(self, node, num):
self.node = node
self.num = num

queue = deque([Pair(root, 0)])
ans = 0

while queue:
n = len(queue)
idx = queue[0].num
first, last = 0, 0

for i in range(n):
curridx = queue[0].num - idx
node = queue.popleft().node

if i == 0:
first = curridx
if i == n - 1:
last = curridx

if node.left:
queue.append(Pair(node.left, curridx * 2 + 1))
if node.right:
queue.append(Pair(node.right, curridx * 2 + 2))

ans = max(last - first + 1, ans)

return ans``````

leet Code : Validate Binary Search Tree Java || C++ || C || pYthon

### Java: Level Order maximum width of binary tree

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

class Solution {
static class Pair {
TreeNode node;
int num;

Pair(TreeNode node, int num) {
this.node = node;
this.num = num;
}
}

public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;

int ans = 0;

while (!q.isEmpty()) {
int n = q.size();
int idx = q.peek().num;
int first = 0, last = 0;

for (int i = 0; i < n; i++) {
int curridx = q.peek().num - idx;
TreeNode node = q.poll().node;

if (i == 0) {
first = curridx;
}
if (i == n - 1) {
last = curridx;
}

if (node.left != null) {
q.add(new Pair(node.left, curridx * 2 + 1));
}
if (node.right != null) {
q.add(new Pair(node.right, curridx * 2 + 2));
}
}

ans = Math.max(last - first + 1, ans);
}

return ans;
}
}``````

Binary Search Working , Impementation | Search and SortingAlgorithm Leet Code | Binary Search in easy way

### JavaScript: Level Order maximum width of binary tree

``````class Solution {
widthOfBinaryTree(root) {
if (!root) return 0;

class Pair {
constructor(node, num) {
this.node = node;
this.num = num;
}
}

const queue = [new Pair(root, 0)];
let ans = 0;

while (queue.length > 0) {
const n = queue.length;
const idx = queue[0].num;
let first = 0, last = 0;

for (let i = 0; i < n; i++) {
const curridx = queue[0].num - idx;
const node = queue.shift().node;

if (i === 0) {
first = curridx;
}
if (i === n - 1) {
last = curridx;
}

if (node.left) {
queue.push(new Pair(node.left, curridx * 2 + 1));
}
if (node.right) {
queue.push(new Pair(node.right, curridx * 2 + 2));
}
}

ans = Math.max(last - first + 1, ans);
}

return ans;
}
}``````

These code examples should provide the same functionality as the original code you provided.

## Method 2: Preorder Traversal with Count Array

### Algorithm:

1. Create a count array with the size equal to the tree’s height.
2. Traverse the tree using preorder traversal.
3. Increment the count for each level in the count array.
4. Find the maximum value in the count array, which represents the maximum width.

Note : Pre oder Travesal is equivalent to DFS search .

Time Complexity: O(N) (Linear)

Space Complexity: O(h) (h = height of the tree)

## Codes : Pre Order maximum width of binary tree

### C++: Pre Order maximum width of binary tree

``````class Solution {
public:
// Function to traverse the binary tree and calculate the maximum width
void calculateWidth(TreeNode* root, int level, long index, vector<long>& startOfLevel, long& maxWidth) {
if (root == nullptr)
return;
if (startOfLevel.size() == level)
startOfLevel.push_back(index);

// Calculate the maximum width at the current level
maxWidth = max(maxWidth, index - startOfLevel[level] + 1);

// Recursive calls for left and right children
calculateWidth(root->left, level + 1, index * 2, startOfLevel, maxWidth);
calculateWidth(root->right, level + 1, index * 2 + 1, startOfLevel, maxWidth);
}

// Main function to find the maximum width of the binary tree
int widthOfBinaryTree(TreeNode* root) {
if (root == nullptr)
return 0;

long maxWidth = 0;
calculateWidth(root, 0, 1, {}, maxWidth);
return maxWidth;
}
};``````

Leet Code : Validate Binary Search Tree Java | CPP | Python solution

### Python: Pre Order maximum width of binary tree

``````class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
def calculate_width(node, level, index, start_of_level, max_width):
if not node:
return
if len(start_of_level) == level:
start_of_level.append(index)

max_width[0] = max(max_width[0], index - start_of_level[level] + 1)

calculate_width(node.left, level + 1, index * 2, start_of_level, max_width)
calculate_width(node.right, level + 1, index * 2 + 1, start_of_level, max_width)

if not root:
return 0

max_width = [0]
calculate_width(root, 0, 1, [], max_width)
return max_width[0]``````

### Java: Pre Order maximum width of binary tree

``````class Solution {
public int widthOfBinaryTree(TreeNode root) {
return calculateWidth(root, 0, 1, new ArrayList<>(), new long[1]);
}

private int calculateWidth(TreeNode node, int level, long index, List<Long> startOfLevel, long[] maxWidth) {
if (node == null)
return 0;

if (startOfLevel.size() == level)

maxWidth[0] = Math.max(maxWidth[0], index - startOfLevel.get(level) + 1);

int leftWidth = calculateWidth(node.left, level + 1, index * 2, startOfLevel, maxWidth);
int rightWidth = calculateWidth(node.right, level + 1, index * 2 + 1, startOfLevel, maxWidth);

return Math.max(leftWidth, rightWidth);
}
}``````

### JavaScript: Pre Order maximum width of binary tree

``````class Solution {
widthOfBinaryTree(root) {
const maxWidth = [0];
this.calculateWidth(root, 0, 1, [], maxWidth);
return maxWidth[0];
}

calculateWidth(node, level, index, startOfLevel, maxWidth) {
if (!node)
return;

if (startOfLevel.length === level)
startOfLevel.push(index);

maxWidth[0] = Math.max(maxWidth[0], index - startOfLevel[level] + 1);

this.calculateWidth(node.left, level + 1, index * 2, startOfLevel, maxWidth);
this.calculateWidth(node.right, level + 1, index * 2 + 1, startOfLevel, maxWidth);
}
}``````

## Method 3: Special Form of Level Order Traversal

### Algorithm:

1. Use a queue to perform level order traversal with two loops.
2. In the inner loop, traverse nodes of a single level.
3. Assign an index to each node based on its position.
4. Calculate and update the maximum width during traversal.

Time Complexity: O(N) (Linear)

Space Complexity: O(N)

Example:
Consider the following binary tree:

``````            1
/   \
2     3
/ \     \
4   5     8
/ \
6   7``````

For this tree, the maximum width is 3.

Conclusion:
Understanding and calculating the maximum width of a binary tree is crucial in various computer science applications. The methods discussed here offer different approaches to solving this problem efficiently. By leveraging these techniques, you can analyze binary trees effectively in your algorithms and data structures endeavors.