Problem Submissions Solution

Maximum Width of Binary Tree

Difficulty: Easy

Acceptance: %

Points: 20.00

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

The maximum width of a tree is the maximum width among all levels.

Given the root of a binary tree, return the maximum width of the given tree.

Topics

Companies

Articles

Examples:

Input: root = [10, 20, 30, 40, 60]

Output: 2

Explanation: There is one node on level 1(10) There is two node on level 2(20, 30) There is two node on level 3(40, 60) Hence the answer is 2

Input: root = [1, 2, 3]

Output: 2

Explanation: On the first level there is only one node 1. On the second level there are two nodes 2, 3 clearly it is the maximum number of nodes at any level

Expected Time Complexity: O(n).

Expected Auxiliary Space: O(width of the tree).

Constraints:
  • 1 <= number of nodes<= 10^5
  • 0 <= node->data <= 10^5
Companies:
Amazon Flipkart
Topics:
Tree
Locked Content
Access Restricted: Please Login to access the code editor and test cases.