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