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) {
        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;
    }
}

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;

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

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)
            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:

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.