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.
Method 1: Level Order Traversal using Queue
Algorithm:
- Initialize a queue and enqueue the root node.
- While the queue is not empty:
a. Dequeue the front node and process it.
b. Enqueue its child nodes (if any). - 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) {
Queue<pair>q=new LinkedList<>();
q.add(new pair(root,0));
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){
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;
}
}
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 ansleet 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;
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(root, 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;
}
}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:
- Create a count array with the size equal to the tree’s height.
- Traverse the tree using preorder traversal.
- Increment the count for each level in the count array.
- 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)
startOfLevel.add(index);
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:
- Use a queue to perform level order traversal with two loops.
- In the inner loop, traverse nodes of a single level.
- Assign an index to each node based on its position.
- 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 7For 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.