Maximum width Using a Special form of level Order Traversal
We will perform a special level order traversal with two loops where inner loops traverses the nodes of a single level. This is to ensure that we can do our calculations once a single level is traversed. In the traversal, we will assign an index to a node.
Below is the implementation of the above Approach:
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node * left, * right;
};
int widthOfBinaryTree(node * root) {
if (!root)
return 0;
int ans = 0;
queue < pair < node * , int >> q;
q.push({
root,
0
});
while (!q.empty()) {
int size = q.size();
int curMin = q.front().second;
int leftMost, rightMost;
for (int i = 0; i < size; i++) {
int cur_id = q.front().second - curMin; // subtracted to prevent integer overflow
node * temp = q.front().first;
q.pop();
if (i == 0) leftMost = cur_id;
if (i == size - 1) rightMost = cur_id;
if (temp -> left)
q.push({
temp -> left,
cur_id * 2 + 1
});
if (temp -> right)
q.push({
temp -> right,
cur_id * 2 + 2
});
}
ans = max(ans, rightMost - leftMost + 1);
}
return ans;
}
struct node * newNode(int data) {
struct node * node = (struct node * ) malloc(sizeof(struct node));
node -> data = data;
node -> left = NULL;
node -> right = NULL;
return (node);
}
int main() {
struct node * root = newNode(1);
root -> left = newNode(3);
root -> left -> left = newNode(5);
root -> left -> left -> left = newNode(7);
root -> right = newNode(2);
root -> right -> right = newNode(4);
root -> right -> right -> right = newNode(6);
int maxWidth = widthOfBinaryTree(root);
cout << "The maximum width of the Binary Tree is " << maxWidth;
return 0;
}
//This code is given by Kushagra Mishra.
/*package whatever //do not write package name here */
import java.util.*;
class TreeNode {
int data;
TreeNode left, right;
TreeNode(int data)
{
this.data=data;
left=null;
right=null;
}
}
class Pair {
TreeNode node;
int num;
Pair(TreeNode _node, int _num) {
num = _num;
node = _node;
}
}
class Solution {
public static int widthOfBinaryTree(TreeNode root) {
if(root == null) return 0;
int ans = 0;
Queue<Pair> q = new LinkedList<>();
q.offer(new Pair(root, 0));
while(!q.isEmpty()){
int size = q.size();
int mmin = q.peek().num; //to make the id starting from zero
int first = 0,last = 0;
for(int i=0; i<size; i++){
int cur_id = q.peek().num-mmin;
TreeNode node = q.peek().node;
q.poll();
if(i==0) first = cur_id;
if(i==size-1) last = cur_id;
if(node.left != null)
q.offer(new Pair(node.left, cur_id*2+1));
if(node.right != null)
q.offer(new Pair(node.right, cur_id*2+2));
}
ans = Math.max(ans, last-first+1);
}
return ans;
}
public static void main(String args[]) {
TreeNode root = new TreeNode(1);
root . left = new TreeNode(3);
root . left . left = new TreeNode(5);
root . left . left . left = new TreeNode(7);
root . right = new TreeNode(2);
root . right . right = new TreeNode(4);
root . right . right . right = new TreeNode(6);
int maxWidth = widthOfBinaryTree(root);
System.out.println("The maximum width of the Binary Tree is "+maxWidth);
//This code is given by Kushagra Mishra.
}
}
# Python program to find the maximum width of
# binary tree using Preorder Traversal.
from collections import deque
# A binary tree node
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# function to find the width of binary tree
def widthOfBinaryTree(root):
if not root:
return 0
ans = 0
q = deque([(root, 0)])
while q:
size = len(q)
cur_min = q[0][1]
left_most, right_most = None, None
for i in range(size):
cur_id = q[0][1] - cur_min # subtracted to prevent integer overflow
temp, _ = q.popleft()
if i == 0:
left_most = cur_id
if i == size - 1:
right_most = cur_id
if temp.left:
q.append((temp.left, cur_id * 2 + 1))
if temp.right:
q.append((temp.right, cur_id * 2 + 2))
ans = max(ans, right_most - left_most + 1)
return ans
# Utility function to create a new node
def newNode(data):
node = Node(data)
return node
# Driver code to test above functions
def main():
root = newNode(1)
root.left = newNode(3)
root.left.left = newNode(5)
root.left.left.left = newNode(7)
root.right = newNode(2)
root.right.right = newNode(4)
root.right.right.right = newNode(6)
maxWidth = widthOfBinaryTree(root)
print("The maximum width of the Binary Tree is", maxWidth)
if __name__ == "__main__":
main()
using System;
using System.Collections.Generic;
public class Node
{
public int Data;
public Node Left;
public Node Right;
}
public class BinaryTree
{
public static int WidthOfBinaryTree(Node root)
{
if (root == null)
return 0;
int maxWidth = 0;
Queue<Tuple<Node, int>> queue = new Queue<Tuple<Node, int>>();
queue.Enqueue(new Tuple<Node, int>(root, 0));
while (queue.Count > 0)
{
int size = queue.Count;
int curMin = queue.Peek().Item2;
int leftMost = 0, rightMost = 0;
for (int i = 0; i < size; i++)
{
Tuple<Node, int> current = queue.Dequeue();
// subtracted to prevent integer overflow
int curId = current.Item2 - curMin;
Node temp = current.Item1;
if (i == 0)
leftMost = curId;
if (i == size - 1)
rightMost = curId;
if (temp.Left != null)
queue.Enqueue(new Tuple<Node, int>(temp.Left, curId * 2 + 1));
if (temp.Right != null)
queue.Enqueue(new Tuple<Node, int>(temp.Right, curId * 2 + 2));
}
maxWidth = Math.Max(maxWidth, rightMost - leftMost + 1);
}
return maxWidth;
}
}
public class GFG
{
public static void Main()
{
Node root = new Node { Data = 1 };
root.Left = new Node { Data = 3 };
root.Left.Left = new Node { Data = 5 };
root.Left.Left.Left = new Node { Data = 7 };
root.Right = new Node { Data = 2 };
root.Right.Right = new Node { Data = 4 };
root.Right.Right.Right = new Node { Data = 6 };
int maxWidth = BinaryTree.WidthOfBinaryTree(root);
Console.WriteLine("The maximum width of the Binary Tree is " + maxWidth);
}
}
// JavaScript Program for the above approach
// A binary Tree Node Structure
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// function to find the width of binary tree
function widthOfBinaryTree(root) {
if (!root) {
return 0;
}
let maxWidth = 0;
const queue = [[root, 0]];
while (queue.length > 0) {
const size = queue.length;
const curMin = queue[0][1];
let leftMost, rightMost;
for (let i = 0; i < size; i++) {
const [temp, curId] = queue.shift();
if (i === 0) {
leftMost = curId;
}
if (i === size - 1) {
rightMost = curId;
}
if (temp.left) {
queue.push([temp.left, curId * 2 + 1]);
}
if (temp.right) {
queue.push([temp.right, curId * 2 + 2]);
}
}
maxWidth = Math.max(maxWidth, rightMost - leftMost + 1);
}
return maxWidth;
}
// Utility function to create a new node
function newNode(data) {
const node = new Node(data);
return node;
}
// Driver code to test above functions
const root = newNode(1);
root.left = newNode(3);
root.left.left = newNode(5);
root.left.left.left = newNode(7);
root.right = newNode(2);
root.right.right = newNode(4);
root.right.right.right = newNode(6);
const maxWidth = widthOfBinaryTree(root);
console.log("The maximum width of the Binary Tree is " + maxWidth);
// THIS CODE IS CONTRIBUTED BY PIYUSH AGARWAL
Output
The maximum width of the Binary Tree is 8
Time Complexity : O(N)
Space Complexity : O(N)
Maximum width of a Binary Tree
Given a binary tree, the task is to find the maximum width of the given tree. The width of a tree is the maximum of the widths of all levels. Before solving the problem first, let us understand what we have to do. Binary trees are one of the most common types of trees in computer science. They are also called “balanced” trees because all of their nodes have an equal number of children. In this case, we will focus on finding the maximum value of W, which is the width of a binary tree. For example, given a binary tree with root node A, which has two children B and C, where B has two children D and E and C has one child F, the maximum width is 3.
The maximum width of a binary tree is the number of nodes at any level. In other words, it is the minimum number of nodes in a tree that can be traversed before you need to make a choice on which node to visit next.
Example:
Input:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
Output: 3
Explanation: For the above tree,
width of level 1 is 1,
width of level 2 is 2,
width of level 3 is 3
width of level 4 is 2.
So the maximum width of the tree is 3.