[Algorithm/DS] Leetcode#662. Maximum Width of Binary Tree

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

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

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.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

Example 2:

Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).

Example 3:

Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width exists in the second level with length 2 (3,2).

Constraints:

  • The number of nodes in the tree is in the range [1, 3000].
  • -100 <= Node.val <= 100

Solution:

Lets take an example of below complete binary tree. You might notice that every level, if the number of nodes = n, next level has 2*n nodes present.

Also if we give an index to every node, at every level we can calculate the node position/index as follows:
Left node is positioned at 2i and Right node is positioned at 2i+1 where i is the index of current node we are exploring.
Lets take an example of root node at i=1. So in the next level left node would be at position: 2 * 1 = 2 and right node would be at position: 2 * 1+ 1= 3.

How about we use this idea to find out the width of the tree at any level ?

So in that case what would be the maximum width of the tree here ?
The maximum nodes are at level(d)=4 and width can be calculated with formula as follows:
width_level = maximum node position — minimum node position + 1

= 15–8+1 = 8

Complete Binary Tree

Time Complexity: O(N) ; We go through every single node traverse through entire tree.
Space Complexity: O(N)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
svalak

svalak

Passionate about problem solving; #WritesOnQuora #VoraciousReader #MBTIEnthusiast #LovePsychology https://www.quora.com/profile/Shaila-Hegde-2