662. Maximum Width of Binary Tree - Explanation

Description

Return the largest width among all levels of the binary tree. A level's width spans from its leftmost present node to its rightmost present node, counting both endpoints and every missing position between them as if the tree were complete. Missing positions outside those endpoints do not contribute.

Node values do not affect the width. A level containing only one node has width 1, even if that node is far to the right in the complete-tree layout. The answer is guaranteed to fit in a signed 32-bit integer.

Input examples use a compact level-order encoding: after the root, each present node contributes left and right child entries in queue order. null marks a missing child, and trailing missing entries may be omitted. This compact input can omit gaps that must still be counted when measuring a level's width.

Example 1:

Maximum Width of Binary Tree, example 1: illustration of the example

Input: root = [8,4,9,1,null,null,2]

Output: 4

Explanation: At depth 2, the complete-tree positions are [1,null,null,2]. The two present endpoints span four positions, so the maximum width is 4.

Example 2:

Maximum Width of Binary Tree, example 2: illustration of the example

Input: root = [8,null,9,null,2]

Output: 1

Explanation: Each level contains only one node. Empty positions to the left of that node are outside the two endpoints and do not add to its width, so the answer is 1.

Example 3:

Maximum Width of Binary Tree, example 3: illustration of the example

Input: root = [8,4,9,null,1,2]

Output: 2

Explanation: The two deepest nodes occupy adjacent complete-tree positions. Their width is 2; the level above also has width 2.

Constraints:

The tree contains between 1 and 3000 nodes.
-100 <= Node.val <= 100
The maximum width is at most 2147483647.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Tree Basics - Understanding tree structure, nodes, and parent-child relationships
Breadth-First Search (BFS) - Level-order traversal using a queue data structure
Depth-First Search (DFS) - Recursive tree traversal techniques
Tree Node Indexing - Assigning positional indices to nodes (left child = 2i, right child = 2i+1)

1. Breadth First Search

Intuition

The width of a level is defined by the distance between the leftmost and rightmost non-null nodes, including any null nodes in between. To measure this, we assign each node a position number: the root is 1, and for any node at position p, its left child is at 2 * p and right child at 2 * p + 1. Using BFS, we traverse level by level and compute the width as the difference between the last and first position on each level, plus one.

Algorithm

Initialize res = 0 and a queue with (root, 1, 0) representing (node, position, level).
Track prevLevel and prevNum to record the first position on each level.
While the queue is not empty:
- Dequeue (node, num, level).
- If level > prevLevel, update prevLevel and prevNum to the current level and position.
- Update res = max(res, num - prevNum + 1).
- Enqueue the left child with position 2 * num and the right child with 2 * num + 1, both at level + 1.
Return res.

# 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: Optional[TreeNode]) -> int:
        res = 0
        q = deque([(root, 1, 0)])  # [node, num, level]
        prevLevel, prevNum = 0, 1

        while q:
            node, num, level = q.popleft()

            if level > prevLevel:
                prevLevel = level
                prevNum = num

            res = max(res, num - prevNum + 1)
            if node.left:
                q.append((node.left, 2 * num, level + 1))
            if node.right:
                q.append((node.right, 2 * num + 1, level + 1))

        return res

/**
 * 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;
 *     }
 * }
 */
public class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;

        int res = 0;
        Queue<Tuple> queue = new LinkedList<>();
        queue.offer(new Tuple(root, 1, 0)); // [node, num, level]
        int prevLevel = 0, prevNum = 1;

        while (!queue.isEmpty()) {
            Tuple current = queue.poll();
            TreeNode node = current.node;
            int num = current.num;
            int level = current.level;

            if (level > prevLevel) {
                prevLevel = level;
                prevNum = num;
            }

            res = Math.max(res, num - prevNum + 1);
            if (node.left != null) {
                queue.offer(new Tuple(node.left, 2 * num, level + 1));
            }
            if (node.right != null) {
                queue.offer(new Tuple(node.right, 2 * num + 1, level + 1));
            }
        }

        return res;
    }

    class Tuple {
        TreeNode node;
        int num, level;

        Tuple(TreeNode node, int num, int level) {
            this.node = node;
            this.num = num;
            this.level = level;
        }
    }
}

/**
 * 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;

        int res = 0;
        queue<tuple<TreeNode*, uint, int>> q; // [node, num, level]
        q.push({root, 1, 0});
        int prevLevel = 0, prevNum = 1;

        while (!q.empty()) {
            auto [node, num, level] = q.front();
            q.pop();

            if (level > prevLevel) {
                prevLevel = level;
                prevNum = num;
            }

            res = max(res, int(num - prevNum) + 1);
            if (node->left) {
                q.push({node->left, 2 * num, level + 1});
            }
            if (node->right) {
                q.push({node->right, 2 * num + 1, level + 1});
            }
        }

        return res;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    widthOfBinaryTree(root) {
        if (!root) return 0;

        let res = 0n;
        const queue = new Queue([[root, 1n, 0]]); // [node, num, level]
        let prevLevel = 0,
            prevNum = 1n;

        while (!queue.isEmpty()) {
            const [node, num, level] = queue.pop();

            if (level > prevLevel) {
                prevLevel = level;
                prevNum = num;
            }

            res = res > num - prevNum + 1n ? res : num - prevNum + 1n;
            if (node.left) {
                queue.push([node.left, 2n * num, level + 1]);
            }
            if (node.right) {
                queue.push([node.right, 2n * num + 1n, level + 1]);
            }
        }

        return Number(res);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func widthOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }

    res := 0
    type item struct {
        node  *TreeNode
        num   uint64
        level int
    }
    queue := []item{{root, 1, 0}}
    prevLevel := 0
    var prevNum uint64 = 1

    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        node, num, level := cur.node, cur.num, cur.level

        if level > prevLevel {
            prevLevel = level
            prevNum = num
        }

        width := int(num - prevNum + 1)
        if width > res {
            res = width
        }
        if node.Left != nil {
            queue = append(queue, item{node.Left, 2 * num, level + 1})
        }
        if node.Right != nil {
            queue = append(queue, item{node.Right, 2*num + 1, level + 1})
        }
    }

    return res
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun widthOfBinaryTree(root: TreeNode?): Int {
        if (root == null) return 0

        var res = 0
        val queue = ArrayDeque<Triple<TreeNode, Long, Int>>()
        queue.add(Triple(root, 1L, 0))
        var prevLevel = 0
        var prevNum = 1L

        while (queue.isNotEmpty()) {
            val (node, num, level) = queue.removeFirst()

            if (level > prevLevel) {
                prevLevel = level
                prevNum = num
            }

            res = maxOf(res, (num - prevNum + 1).toInt())
            node.left?.let { queue.add(Triple(it, 2 * num, level + 1)) }
            node.right?.let { queue.add(Triple(it, 2 * num + 1, level + 1)) }
        }

        return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func widthOfBinaryTree(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }

        var res = 0
        var queue: [(TreeNode, UInt64, Int)] = [(root, 1, 0)]
        var prevLevel = 0
        var prevNum: UInt64 = 1

        while !queue.isEmpty {
            let (node, num, level) = queue.removeFirst()

            if level > prevLevel {
                prevLevel = level
                prevNum = num
            }

            res = max(res, Int(num - prevNum + 1))
            if let left = node.left {
                queue.append((left, 2 * num, level + 1))
            }
            if let right = node.right {
                queue.append((right, 2 * num + 1, level + 1))
            }
        }

        return res
    }
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//     pub val: i32,
//     pub left: Option<Rc<RefCell<TreeNode>>>,
//     pub right: Option<Rc<RefCell<TreeNode>>>,
// }
impl Solution {
    pub fn width_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let root = match root {
            Some(r) => r,
            None => return 0,
        };

        let mut res: u64 = 0;
        // (node, num, level)
        let mut queue: VecDeque<(Rc<RefCell<TreeNode>>, u64, i32)> = VecDeque::new();
        queue.push_back((root, 1, 0));
        let mut prev_level = 0;
        let mut prev_num: u64 = 1;

        while let Some((node, num, level)) = queue.pop_front() {
            if level > prev_level {
                prev_level = level;
                prev_num = num;
            }

            res = res.max(num - prev_num + 1);
            let node_ref = node.borrow();
            if let Some(ref left) = node_ref.left {
                queue.push_back((Rc::clone(left), 2 * num, level + 1));
            }
            if let Some(ref right) = node_ref.right {
                queue.push_back((Rc::clone(right), 2 * num + 1, level + 1));
            }
        }

        res as i32
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Breadth First Search (Optimal)

Intuition

Position numbers can grow large in deep skewed trees, potentially causing overflow. To prevent this, we normalize positions at each level by subtracting the starting position of that level. This keeps the numbers small while still correctly computing the width as the difference between the rightmost and leftmost positions on each level.

Algorithm

Initialize res = 0 and a queue with (root, 0).
While the queue is not empty:
- Record start as the position of the first node in the current level.
- For each node in the current level:
  - Compute curNum = num - start to normalize.
  - Update res = max(res, curNum + 1).
  - Enqueue children with positions 2 * curNum and 2 * curNum + 1.
Return res.

# 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: Optional[TreeNode]) -> int:
        res = 0
        q = deque([(root, 0)])

        while q:
            start = q[0][1]
            for _ in range(len(q)):
                node, num = q.popleft()
                curNum = num - start
                res = max(res, curNum + 1)
                if node.left:
                    q.append((node.left, 2 * curNum))
                if node.right:
                    q.append((node.right, 2 * curNum + 1))

        return res

/**
 * 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;
 *     }
 * }
 */
public class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        int res = 0;
        Queue<Pair<TreeNode, Integer>> q = new LinkedList<>();
        q.offer(new Pair<>(root, 0));

        while (!q.isEmpty()) {
            int start = q.peek().getValue();
            for (int i = q.size(); i > 0; i--) {
                Pair<TreeNode, Integer> pair = q.poll();
                TreeNode node = pair.getKey();
                int num = pair.getValue() - start;

                res = Math.max(res, num + 1);
                if (node.left != null) {
                    q.offer(new Pair<>(node.left, 2 * num));
                }
                if (node.right != null) {
                    q.offer(new Pair<>(node.right, 2 * num + 1));
                }
            }
        }

        return res;
    }
}

/**
 * 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) {
        int res = 0;
        queue<pair<TreeNode*, uint>> q;
        q.push({root, 0});

        while (!q.empty()) {
            int start = q.front().second;

            for (int i = q.size(); i > 0; --i) {
                auto [node, num] = q.front();
                q.pop();
                uint curNum = num - start;
                res = max(res, int(curNum) + 1);
                if (node->left) {
                    q.push({node->left, 2 * curNum});
                }
                if (node->right) {
                    q.push({node->right, 2 * curNum + 1});
                }
            }
        }

        return res;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    widthOfBinaryTree(root) {
        let res = 0;
        const q = new Queue([[root, 0]]);

        while (!q.isEmpty()) {
            const start = q.front()[1];

            for (let i = q.size(); i > 0; i--) {
                const [node, num] = q.pop();
                const curNum = num - start;
                res = Math.max(res, curNum + 1);
                if (node.left) {
                    q.push([node.left, 2 * curNum]);
                }
                if (node.right) {
                    q.push([node.right, 2 * curNum + 1]);
                }
            }
        }

        return res;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func widthOfBinaryTree(root *TreeNode) int {
    res := 0
    type item struct {
        node *TreeNode
        num  uint
    }
    queue := []item{{root, 0}}

    for len(queue) > 0 {
        start := queue[0].num
        size := len(queue)

        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]
            curNum := cur.num - start
            if int(curNum)+1 > res {
                res = int(curNum) + 1
            }
            if cur.node.Left != nil {
                queue = append(queue, item{cur.node.Left, 2 * curNum})
            }
            if cur.node.Right != nil {
                queue = append(queue, item{cur.node.Right, 2*curNum + 1})
            }
        }
    }

    return res
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun widthOfBinaryTree(root: TreeNode?): Int {
        var res = 0
        val queue = ArrayDeque<Pair<TreeNode, Int>>()
        queue.add(root!! to 0)

        while (queue.isNotEmpty()) {
            val start = queue.first().second
            val size = queue.size

            repeat(size) {
                val (node, num) = queue.removeFirst()
                val curNum = num - start
                res = maxOf(res, curNum + 1)
                node.left?.let { queue.add(it to 2 * curNum) }
                node.right?.let { queue.add(it to 2 * curNum + 1) }
            }
        }

        return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func widthOfBinaryTree(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }

        var res = 0
        var queue: [(TreeNode, Int)] = [(root, 0)]

        while !queue.isEmpty {
            let start = queue.first!.1
            let size = queue.count

            for _ in 0..<size {
                let (node, num) = queue.removeFirst()
                let curNum = num - start
                res = max(res, curNum + 1)
                if let left = node.left {
                    queue.append((left, 2 * curNum))
                }
                if let right = node.right {
                    queue.append((right, 2 * curNum + 1))
                }
            }
        }

        return res
    }
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//     pub val: i32,
//     pub left: Option<Rc<RefCell<TreeNode>>>,
//     pub right: Option<Rc<RefCell<TreeNode>>>,
// }
impl Solution {
    pub fn width_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let root = match root {
            Some(r) => r,
            None => return 0,
        };

        let mut res: u64 = 0;
        let mut queue: VecDeque<(Rc<RefCell<TreeNode>>, u64)> = VecDeque::new();
        queue.push_back((root, 0));

        while !queue.is_empty() {
            let start = queue.front().unwrap().1;
            let size = queue.len();

            for _ in 0..size {
                let (node, num) = queue.pop_front().unwrap();
                let cur_num = num - start;
                res = res.max(cur_num + 1);
                let node_ref = node.borrow();
                if let Some(ref left) = node_ref.left {
                    queue.push_back((Rc::clone(left), 2 * cur_num));
                }
                if let Some(ref right) = node_ref.right {
                    queue.push_back((Rc::clone(right), 2 * cur_num + 1));
                }
            }
        }

        res as i32
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Depth First Search

Intuition

We can also solve this with DFS by recording the first position encountered at each level. As we traverse, whenever we visit a node, we check if its level has been seen before. If not, we record its position as the first for that level. The width at any node is computed as the difference from the first position on its level. We normalize child positions to avoid overflow.

Algorithm

Maintain a map first where first[level] stores the position of the first node visited at that level.
Define dfs(node, level, curNum):
- If node is null, return.
- If level not in first, set first[level] = curNum.
- Update res = max(res, curNum - first[level] + 1).
- Recurse on left child with level + 1 and position 2 * (curNum - first[level]).
- Recurse on right child with level + 1 and position 2 * (curNum - first[level]) + 1.
Call dfs(root, 0, 0) and return res.

# 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: Optional[TreeNode]) -> int:
        first = {}
        res = 0

        def dfs(node, level, num):
            nonlocal res
            if not node:
                return

            if level not in first:
                first[level] = num

            res = max(res, num - first[level] + 1)
            dfs(node.left, level + 1, 2 * num)
            dfs(node.right, level + 1, 2 * num + 1)

        dfs(root, 0, 0)
        return res

/**
 * 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;
 *     }
 * }
 */
public class Solution {
    private Map<Integer, Integer> first;
    public int widthOfBinaryTree(TreeNode root) {
        first = new HashMap<>();
        int[] res = new int[1];

        dfs(root, 0, 0, res);
        return res[0];
    }

    private void dfs(TreeNode node, int level, int num, int[] res) {
        if (node == null) {
            return;
        }

        first.putIfAbsent(level, num);
        res[0] = Math.max(res[0], num - first.get(level) + 1);
        dfs(node.left, level + 1, 2 * num, res);
        dfs(node.right, level + 1, 2 * num + 1, res);
    }
}

/**
 * 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 {
    unordered_map<int, unsigned long long> first;

public:
    int widthOfBinaryTree(TreeNode* root) {
        unsigned long long res = 0;

        dfs(root, 0, 0, res);
        return int(res);
    }

private:
    void dfs(TreeNode* node, int level, unsigned long long num, unsigned long long& res) {
        if (!node) {
            return;
        }

        if (!first.count(level)) {
            first[level] = num;
        }

        res = max(res, num - first[level] + 1);
        dfs(node->left, level + 1, 2 * (num - first[level]), res);
        dfs(node->right, level + 1, 2 * (num - first[level]) + 1, res);
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    widthOfBinaryTree(root) {
        const first = new Map();
        let res = 0;

        const dfs = (node, level, curNum) => {
            if (!node) return;

            if (!first.has(level)) {
                first.set(level, curNum);
            }

            res = Math.max(res, curNum - first.get(level) + 1);
            dfs(node.left, level + 1, 2 * (curNum - first.get(level)));
            dfs(node.right, level + 1, 2 * (curNum - first.get(level)) + 1);
        };

        dfs(root, 0, 0);
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func widthOfBinaryTree(root *TreeNode) int {
    first := make(map[int]int)
    res := 0

    var dfs func(node *TreeNode, level, curNum int)
    dfs = func(node *TreeNode, level, curNum int) {
        if node == nil {
            return
        }

        if _, ok := first[level]; !ok {
            first[level] = curNum
        }

        width := curNum - first[level] + 1
        if width > res {
            res = width
        }
        dfs(node.Left, level+1, 2*(curNum-first[level]))
        dfs(node.Right, level+1, 2*(curNum-first[level])+1)
    }

    dfs(root, 0, 0)
    return res
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    private val first = mutableMapOf<Int, Int>()
    private var res = 0

    fun widthOfBinaryTree(root: TreeNode?): Int {
        first.clear()
        res = 0
        dfs(root, 0, 0)
        return res
    }

    private fun dfs(node: TreeNode?, level: Int, curNum: Int) {
        if (node == null) return

        if (level !in first) {
            first[level] = curNum
        }

        res = maxOf(res, curNum - first[level]!! + 1)
        dfs(node.left, level + 1, 2 * (curNum - first[level]!!))
        dfs(node.right, level + 1, 2 * (curNum - first[level]!!) + 1)
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    private var first = [Int: Int]()
    private var res = 0

    func widthOfBinaryTree(_ root: TreeNode?) -> Int {
        first = [:]
        res = 0
        dfs(root, 0, 0)
        return res
    }

    private func dfs(_ node: TreeNode?, _ level: Int, _ curNum: Int) {
        guard let node = node else { return }

        if first[level] == nil {
            first[level] = curNum
        }

        res = max(res, curNum - first[level]! + 1)
        dfs(node.left, level + 1, 2 * (curNum - first[level]!))
        dfs(node.right, level + 1, 2 * (curNum - first[level]!) + 1)
    }
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//     pub val: i32,
//     pub left: Option<Rc<RefCell<TreeNode>>>,
//     pub right: Option<Rc<RefCell<TreeNode>>>,
// }
impl Solution {
    pub fn width_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut first: HashMap<i32, u64> = HashMap::new();
        let mut res: u64 = 0;

        fn dfs(
            node: &Option<Rc<RefCell<TreeNode>>>,
            level: i32, cur_num: u64,
            first: &mut HashMap<i32, u64>, res: &mut u64,
        ) {
            let node = match node {
                Some(n) => n,
                None => return,
            };

            first.entry(level).or_insert(cur_num);
            let f = *first.get(&level).unwrap();
            *res = (*res).max(cur_num - f + 1);

            let node_ref = node.borrow();
            dfs(&node_ref.left, level + 1, 2 * (cur_num - f), first, res);
            dfs(&node_ref.right, level + 1, 2 * (cur_num - f) + 1, first, res);
        }

        dfs(&root, 0, 0, &mut first, &mut res);
        res as i32
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Integer Overflow from Position Numbers

Position numbers double at each level (2 * num for left child, 2 * num + 1 for right). In a deep, skewed tree, these values can overflow standard integer types. Use larger types like unsigned long long in C++ or BigInt in JavaScript, or normalize positions by subtracting the starting position at each level.

Miscounting the Width

Width is defined as the number of nodes between the leftmost and rightmost positions on a level, inclusive. The formula is rightmost - leftmost + 1, not just the difference. Forgetting the + 1 gives a width that is one less than correct.

Incorrect Level Tracking in BFS

When processing nodes level by level, you must correctly identify the first node of each new level to record its starting position. If you mix up the level boundaries or fail to update the starting position when entering a new level, the width calculation will be incorrect.