Grokking the Coding Interview: The Original Course
Vote

0% completed

​

Solution: Maximum Width of Binary Tree

Problem Statement

Given the root of a binary tree, find the maximum width of the tree.

The maximum width is the widest level in the tree.

The width of a level is the number of nodes between 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.

You can assume that the result will fit within a 32-bit signed integer.

Examples

Example 1

  • Input: root = [1, 2, 3, 4, null, null, 5]
  • Output: 4

.....

.....

.....

Like the course? Get enrolled and start learning!
Sajid Khan

Sajid Khan

· 20 days ago

class Solution {
    widthOfBinaryTree(root) {
        if (root === null) return 0;
        const queue = [{ node: root, position: 0 }];
        let maxWidth = 1;
        let head = 0;

        while (head < queue.length) {
            const levelSize = queue.length - head;
            let first = 0, last = 0;

            for (let i = 0; i < levelSize; i++) {
                const { node, position } = queue[head++];

                if (i === 0) first = position
                if (i === levelSize - 1) last = position;

                if (node.left)
	                queue.push({ node: node.left, position: position * 2 + 1 })
                if (node.right)
	                queue.push({ node: node.right, position: position * 2 + 2 })
            }

            maxWidth = Mat

Reading Progress

0%

Vote for new content