Solution For Maximum Width Of Binary Tree
Problem Statement:
Given a binary tree, write a function to get the maximum width of the given tree. The maximum width of a tree is defined as the maximum number of nodes in any level. If the tree is empty, return 0.
Example:
Input:
1
/ \
3 2
/ \ \
5 3 9
Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
Solution:
To find the maximum width of the binary tree, we need to traverse the tree level by level and count the number of nodes in each level. We can use a queue for the breadth-first search and a map to store the position of each node in the level.
Algorithm:
Initialize a queue to store the nodes of the tree and a map to store the position of each node.
Start the breadth-first traversal of the binary tree by adding the root to the queue.
While the queue is not empty, process each level of the tree.
For each node in the queue, add its left and right child to the queue and update their positions in the map.
After processing the current level, update the maximum width with the difference between the leftmost and rightmost positions in the level.
Repeat steps 3-5 until the queue is empty.
Return the maximum width of the tree.
Pseudo Code:
function max_width_binary_tree(root: TreeNode) -> int:
if not root:
return 0
queue = [(root, 0)]
level_positions = {}
max_width = 0
while queue:
level_len = len(queue)
for i in range(level_len):
node, pos = queue.pop(0)
level_positions[pos] = node
if node.left:
queue.append((node.left, 2*pos))
if node.right:
queue.append((node.right, 2*pos+1))
level_width = level_positions[max(level_positions)]-level_positions[min(level_positions)]+1
max_width = max(max_width, level_width)
level_positions.clear()
return max_width
Time Complexity:
The time complexity of this algorithm is O(n) as we need to traverse all the nodes of the binary tree.
Space Complexity:
The space complexity of this algorithm is O(n) as we need to store the nodes in the queue and the positions in the map.
Step by Step Implementation For Maximum Width Of Binary Tree
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if(root==null)
return 0;
Queue queue=new LinkedList<>();
queue.add(root);
int maxWidth=1;
while(!queue.isEmpty()){
int count=queue.size();
maxWidth=Math.max(maxWidth,count);
for(int i=0;i# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
# Base case
if not root:
return 0
# Initialize variables
queue = [[root, 0]] # list of [node, position] pairs
max_width = 1 # max width of tree
# Perform breadth first search
while queue:
# Get the size of the current level
size = len(queue)
# Get the left and right most positions of the current level
leftmost = queue[0][1]
rightmost = queue[size - 1][1]
# Update max width if necessary
max_width = max(max_width, rightmost - leftmost + 1)
# Iterate through current level
for i in range(size):
# Get node and position from queue
node, position = queue.pop(0)
# Add children to queue if they exist
if node.left:
queue.append([node.left, 2 * position])
if node.right:
queue.append([node.right, 2 * position + 1])
return max_width/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var widthOfBinaryTree = function(root) {
// edge case - if the tree is empty, return 0
if (!root) return 0;
// create a queue to store the nodes at each level
let queue = [];
// push the root node into the queue
queue.push(root);
// create a variable to store the maximum width
let maxWidth = 0;
// while the queue is not empty
while (queue.length) {
// store the length of the queue in a variable
let queueLength = queue.length;
// if the queue length is greater than the maximum width, update the maximum width
if (queueLength > maxWidth) {
maxWidth = queueLength;
}
// iterate through the queue
for (let i = 0; i < queueLength; i++) {
// store the node at the front of the queue in a variable
let node = queue.shift();
// if the node has a left child, push it into the queue
if (node.left) {
queue.push(node.left);
}
// if the node has a right child, push it into the queue
if (node.right) {
queue.push(node.right);
}
}
}
// return the maximum width
return maxWidth;
};/**
* 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) {}
* };
*/
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if(!root) return 0;
queue> q;
int maxWidth = 0;
q.push({root, 1});
while(!q.empty()){
int count = q.size();
int start = q.front().second, end = q.back().second;
maxWidth = max(maxWidth, end-start+1);
for(int i = 0; i < count; i++){
TreeNode* curr = q.front().first;
int idx = q.front().second;
q.pop();
if(curr->left) q.push({curr->left, 2*idx});
if(curr->right) q.push({curr->right, 2*idx+1});
}
}
return maxWidth;
}
}; /**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public int WidthOfBinaryTree(TreeNode root) {
// Base case
if (root == null) {
return 0;
}
// Queue to store all the nodes at each level
Queue queue = new Queue();
// Variable to store the maximum width
int maxWidth = 0;
// Add the root node to the queue
queue.Enqueue(root);
// Loop through the queue while it's not empty
while (queue.Count != 0) {
// Get the size of the queue
int size = queue.Count;
// Update the maximum width
maxWidth = Math.Max(maxWidth, size);
// Loop through all the nodes in the queue
for (int i = 0; i < size; i++) {
// Get the node from the queue
TreeNode node = queue.Dequeue();
// Add the left child to the queue
if (node.left != null) {
queue.Enqueue(node.left);
}
// Add the right child to the queue
if (node.right != null) {
queue.Enqueue(node.right);
}
}
}
// Return the maximum width
return maxWidth;
}
}