Discovering Binary Tree Width: A Journey from HashMap to Position Formulas

November 14, 2025 · 14 min read

Software Developer

A conversation about solving the Widest Binary Tree Level problem that reveals how mathematical position formulas and DFS traversal create an elegant solution—and why we need to track both min and max positions at each level.

The Problem

Teacher: Today we're tackling an interesting tree problem. Let me show you what we're dealing with:

Problem: Maximum Width of Binary Tree

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

The width of a level is defined as the distance between the leftmost and rightmost non-null nodes in the level, where the null nodes in between are also counted into the length calculation.

Example:

Input: root = [1,3,2,5,3,null,9]

        1
       / \
      3   2
     / \   \
    5   3   9

Output: 4
Explanation: The maximum width is at level 3 with
length 4 (5,3,null,9)

My Initial Approach

Me: Alright, let me share my thoughts on this. I'm thinking about having a recursive function to traverse the tree. We're going to need to track which level we're currently in using a parameter.

In this function, we need to call it for the left node and right node, passing the level information via parameter.

Other than that, outside this function, I want to have a map or some storage mechanism. That will store our level and each node in those levels. Like, integer as key and a list as value in a hashmap maybe.

So we can store the nodes that we have in each level. Like in the first level, we're going to have only one node. In the second level, we're going to have two nodes. And on the third level, we're going to have four nodes and so on—like the power of two.

Teacher: Good start! You're thinking about the right building blocks. But let me ask you something...

The Critical Realization

Teacher: You mentioned storing nodes at each level. But look at the problem again. What does it actually ask for?

Me: [reading again] Oh! It asks: "return the width of the widest level." Where the width is defined as the distance between leftmost and rightmost non-null nodes.

So now that I read the question again, we may need to alter my approach. But the core logic can still stay the same, I believe.

Teacher: Exactly! You don't need to store ALL the nodes. You just need to find the leftmost and rightmost positions. So what information do you REALLY need to track?

Me: We need to know how many nodes are in a level. Or rather, the positions in a level!

Teacher: Good! And how do we know positions? Let me give you a hint: In a binary tree, if a parent node is at position p, where would its children be?

Question 1: The Position Formula Mystery

Teacher: Think about how binary trees are sometimes represented in arrays (like binary heaps). Is there a mathematical relationship between a parent's position and its children's positions?

Me: Hmm... I'm not sure. Can you explain?

Teacher: Sure! There's a beautiful mathematical relationship:

If a parent node is at position p:
  - Its LEFT child is at position: 2 × p
  - Its RIGHT child is at position: 2 × p + 1

Let me show you:

Position 0 (or 1 if you start from 1):
  ├─ Left child: 2 × 0 = 0 (or 2 × 1 = 2)
  └─ Right child: 2 × 0 + 1 = 1 (or 2 × 1 + 1 = 3)

Position 1:
  ├─ Left child: 2 × 1 = 2
  └─ Right child: 2 × 1 + 1 = 3

Position 2:
  ├─ Left child: 2 × 2 = 4
  └─ Right child: 2 × 2 + 1 = 5

Me: Oh! So even if there are null nodes, we can calculate the position mathematically!

Teacher: Exactly! This is how binary heaps work in array representation. You can use this formula to assign positions to nodes during DFS traversal.

Question 2: DFS or BFS?

Me: Since we're using recursion and tracking positions, I guess we need to use breadth-first search? Because I know BFS is best for level-order traversal.

Teacher: Good question! But let me ask you this: Do you need to process all nodes at a level at the same time? Or do you just need to remember the leftmost and rightmost positions you've seen for each level?

Me: Hmm... I just need to track the min and max positions for each level!

Teacher: Exactly! So you CAN use DFS! As you traverse with DFS, you can remember:

"At level 2, the leftmost position I've seen is X"
"At level 2, the rightmost position I've seen is Y"
The width would be Y - X + 1

DFS works perfectly fine for this!

Question 3: What to Store in the HashMap?

Me: Alright, so I need a HashMap where:

Key: level number
Value: ... what exactly?

I guess it would be great if we store the leftmost non-null position and rightmost non-null position in each level. And we need to track the level each node is at via parameter (stateful recursion).

Teacher: Perfect! You're exactly right! So what data structure should the value be?

Me: How about a list? First element can be the leftmost and the second element can be the rightmost?

Teacher: Excellent! So your HashMap would be:

HashMap<Integer, List<Integer>> map
// where map.get(level) returns [leftmost_position, rightmost_position]

Or you could use:

An int[] array of size 2
A custom Pair class
Two separate HashMaps (one for leftmost, one for rightmost)

Any of these work! Let's stick with your List idea.

Question 4: Updating the HashMap

Teacher: Now think about this: When you're in your recursive function and you visit a node at position pos and level level, how do you update the HashMap?

Think about two scenarios:

Scenario A: This is the FIRST node you've visited at this level

What should you put in the list?

Scenario B: You've ALREADY visited other nodes at this level

How do you update the leftmost value?
How do you update the rightmost value?

Me: For the first node, I would set both leftmost and rightmost to the same position:

list.add(position);  // leftmost
list.add(position);  // rightmost

For subsequent nodes, I would use Math.min and Math.max:

list.set(0, Math.min(list.get(0), position));  // update leftmost
list.set(1, Math.max(list.get(1), position));  // update rightmost

Teacher: Brilliant! 🎯 You've got it! So without needing to store all the nodes in a level, we just store the min and max positions!

The Width Formula

Teacher: One more important detail. If a level has:

leftmost position = 4
rightmost position = 7

What's the width? Is it 7 - 4 = 3?

Me: Wait... positions 4, 5, 6, 7 would be 4 positions. So the width should be 7 - 4 + 1 = 4!

Teacher: Exactly! The formula is:

width = rightmost - leftmost + 1

Don't forget the + 1!

Putting It All Together

Me: So let me trace through the algorithm:

Use a recursive function with parameters: node, level, position
Have a HashMap: <level, [leftmost_pos, rightmost_pos]>
For each node:
- Update the HashMap with the current position
- Recurse to left child: position = 2 × p
- Recurse to right child: position = 2 × p + 1
After traversal, find the maximum width across all levels

Teacher: Perfect! You've got the complete picture! Now let's write the code.

The Complete Solution

import java.util.*;

class Solution {
    public int widestLevelWidth(TreeNode root) {
        if (root == null) return 0;

        // HashMap: level -> [leftmost_position, rightmost_position]
        HashMap<Integer, List<Integer>> map = new HashMap<>();

        // Start DFS from root at level 0, position 0
        traverse(root, 0, 0, map);

        // Find maximum width across all levels
        int maxWidth = 0;
        for (List<Integer> bounds : map.values()) {
            int width = bounds.get(1) - bounds.get(0) + 1;
            maxWidth = Math.max(maxWidth, width);
        }

        return maxWidth;
    }

    private void traverse(TreeNode node, int level, int position,
                         HashMap<Integer, List<Integer>> map) {
        // Base case: null node
        if (node == null) {
            return;
        }

        // Update HashMap with current node's position
        if (!map.containsKey(level)) {
            // First node at this level
            List<Integer> list = new ArrayList<>();
            list.add(position);  // leftmost
            list.add(position);  // rightmost
            map.put(level, list);
        } else {
            // Update min/max for this level
            List<Integer> list = map.get(level);
            list.set(0, Math.min(list.get(0), position));  // update leftmost
            list.set(1, Math.max(list.get(1), position));  // update rightmost
        }

        // Recursive calls to children
        traverse(node.left, level + 1, 2 * position, map);
        traverse(node.right, level + 1, 2 * position + 1, map);
    }
}

Complexity:

Time: O(n) - visit each node once
Space: O(h) for recursion stack + O(h) for HashMap where h is height

Wait, What About Position 0?

Me: I have a question. If we start the root at position 0, then:

Left child: 2 × 0 = 0
Right child: 2 × 0 + 1 = 1

But that means the left child also has position 0! Isn't that a problem?

Teacher: Excellent catch! You found an edge case!

You're absolutely right. If you start from position 0, the formula doesn't work correctly. That's why many implementations start from position 1:

// Start from position 1 instead of 0
traverse(root, 0, 1, map);

// Then:
// Left child: 2 × 1 = 2
// Right child: 2 × 1 + 1 = 3

Or you can use a different convention:

// Start from position 0, but use different formulas
// Left child: 2 × p + 1
// Right child: 2 × p + 2

Either works! Just be consistent!

Step-by-Step Trace

Let's trace through the example:

Input: root = [1,3,2,5,3,null,9]

        1
       / \
      3   2
     / \   \
    5   3   9

Starting: traverse(1, level=0, position=1)

map = {}
maxWidth = 0

Visit Node 1 (level 0, position 1):

map = {0: [1, 1]}
Recurse left: traverse(3, 1, 2)
Recurse right: traverse(2, 1, 3)

Visit Node 3 (level 1, position 2):

map = {0: [1, 1], 1: [2, 2]}
Recurse left: traverse(5, 2, 4)
Recurse right: traverse(3, 2, 5)

Visit Node 2 (level 1, position 3):

map = {0: [1, 1], 1: [2, 3]}  // Updated max position
Recurse right: traverse(9, 2, 7)

Visit Node 5 (level 2, position 4):

map = {0: [1, 1], 1: [2, 3], 2: [4, 4]}

Visit Node 3 (level 2, position 5):

map = {0: [1, 1], 1: [2, 3], 2: [4, 5]}

Visit Node 9 (level 2, position 7):

map = {0: [1, 1], 1: [2, 3], 2: [4, 7]}

Calculate widths:

Level 0: 1 - 1 + 1 = 1
Level 1: 3 - 2 + 1 = 2
Level 2: 7 - 4 + 1 = 4  ← Maximum!

Answer: 4 ✓

Common Mistakes

❌ Mistake 1: Forgetting the +1 in Width Calculation

// Wrong:
int width = bounds.get(1) - bounds.get(0);  // Off by one!

// Correct:
int width = bounds.get(1) - bounds.get(0) + 1;

❌ Mistake 2: Starting from Position 0

// Wrong:
traverse(root, 0, 0, map);
// Left child: 2 × 0 = 0 (same as parent!)

// Correct:
traverse(root, 0, 1, map);
// Left child: 2 × 1 = 2
// Right child: 2 × 1 + 1 = 3

❌ Mistake 3: Not Handling Null Nodes

// Wrong: No null check, causes NullPointerException
private void traverse(TreeNode node, int level, int position, ...) {
    map.put(level, ...);  // Crashes if node is null!
    traverse(node.left, ...);
}

// Correct: Check for null first
private void traverse(TreeNode node, int level, int position, ...) {
    if (node == null) return;  // Early return!
    // ... rest of logic
}

❌ Mistake 4: Creating New List Every Time

// Wrong: Overwrites previous min/max
if (!map.containsKey(level)) {
    List<Integer> list = new ArrayList<>();
    list.add(position);
    list.add(position);
    map.put(level, list);
}
// Missing: the ELSE block to update existing list!

// Correct: Update existing list in else block
else {
    List<Integer> list = map.get(level);
    list.set(0, Math.min(list.get(0), position));
    list.set(1, Math.max(list.get(1), position));
}

Alternative Approach: Using int[]

You can simplify the code by using int[] arrays instead of Lists:

class Solution {
    public int widestLevelWidth(TreeNode root) {
        if (root == null) return 0;

        // HashMap: level -> [leftmost, rightmost]
        HashMap<Integer, int[]> map = new HashMap<>();
        traverse(root, 0, 1, map);

        int maxWidth = 0;
        for (int[] bounds : map.values()) {
            int width = bounds[1] - bounds[0] + 1;
            maxWidth = Math.max(maxWidth, width);
        }

        return maxWidth;
    }

    private void traverse(TreeNode node, int level, int position,
                         HashMap<Integer, int[]> map) {
        if (node == null) return;

        if (!map.containsKey(level)) {
            map.put(level, new int[]{position, position});
        } else {
            int[] bounds = map.get(level);
            bounds[0] = Math.min(bounds[0], position);
            bounds[1] = Math.max(bounds[1], position);
        }

        traverse(node.left, level + 1, 2 * position, map);
        traverse(node.right, level + 1, 2 * position + 1, map);
    }
}

This is cleaner and slightly more memory-efficient!

Testing the Solution

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public class TestWidestLevel {
    public static void main(String[] args) {
        Solution sol = new Solution();

        // Test case 1: Example tree
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(3);
        root1.right = new TreeNode(2);
        root1.left.left = new TreeNode(5);
        root1.left.right = new TreeNode(3);
        root1.right.right = new TreeNode(9);
        System.out.println(sol.widestLevelWidth(root1));  // Expected: 4

        // Test case 2: Single node
        TreeNode root2 = new TreeNode(1);
        System.out.println(sol.widestLevelWidth(root2));  // Expected: 1

        // Test case 3: Only left children
        TreeNode root3 = new TreeNode(1);
        root3.left = new TreeNode(2);
        root3.left.left = new TreeNode(3);
        System.out.println(sol.widestLevelWidth(root3));  // Expected: 1

        // Test case 4: Null node
        System.out.println(sol.widestLevelWidth(null));  // Expected: 0
    }
}

The Aha Moment

Me: So the key insight is that we don't need to store all the nodes—we just need to track the minimum and maximum positions at each level using the mathematical position formula!

Teacher: Exactly! And by using DFS with position tracking, we can solve this elegantly in O(n) time with O(h) space.

The formula 2p and 2p+1 is what makes this work—it accounts for null nodes automatically by assigning positions based on the parent's position, not based on what actually exists in the tree.

Key Takeaways

What We Learned

Position Formula for Binary Trees:

If parent is at position p:
  - Left child: 2 × p
  - Right child: 2 × p + 1
(Starting from position 1, not 0!)

DFS Works for Level Problems:
- You don't always need BFS for level-order problems
- DFS can track level information via parameters
- Use a HashMap to aggregate information by level
Min/Max Tracking Pattern:
```
Don't store ALL elements → Just store min and max
```
This saves memory and simplifies logic!
Width Calculation:
```
width = rightmost - leftmost + 1
```
Don't forget the + 1!

HashMap Structure:

HashMap<Integer, int[]> map
// Key: level
// Value: [leftmost_position, rightmost_position]

Stateful Recursion:
- Pass level and position as parameters
- Update global state (HashMap) during traversal
- Base case: if (node == null) return;

The Broader Pattern

This position formula technique appears in many tree problems:

The Core Pattern

// Template for position-based tree traversal
void traverse(TreeNode node, int level, int position, Map state) {
    if (node == null) return;

    // Update state for current level and position
    updateState(state, level, position, node);

    // Recurse with position formula
    traverse(node.left, level + 1, 2 * position, state);
    traverse(node.right, level + 1, 2 * position + 1, state);
}

Conclusion

What started as uncertainty about using DFS vs BFS became clear through mathematical insight:

The position formula 2p and 2p+1 accounts for null nodes automatically
We only need to track min/max positions per level, not all nodes
DFS works perfectly with proper parameter passing
The width formula needs the +1 offset
Starting from position 1 (not 0) makes the math work correctly

The beauty of this solution: It transforms a complex tree width problem into an elegant traversal with mathematical position tracking!

Practice Problems

Try these to solidify your understanding:

Widest Binary Tree Level (our problem) - LeetCode 662
Complete Binary Tree Inserter - LeetCode 919
Count Complete Tree Nodes - LeetCode 222
Binary Tree Level Order Traversal - LeetCode 102

Tags: #algorithms #binary-trees #dfs #hashmap #position-formula #learning-journey #leetcode

This conversation happened during a real algorithm learning session. Sometimes the best solutions come from questioning our initial assumptions—like whether we really need to store all nodes when we only need the boundaries!

The Problem​

My Initial Approach​

The Critical Realization​

Question 1: The Position Formula Mystery​

Question 2: DFS or BFS?​

Question 3: What to Store in the HashMap?​

Question 4: Updating the HashMap​

The Width Formula​

Putting It All Together​

The Complete Solution​

Wait, What About Position 0?​

Step-by-Step Trace​

Common Mistakes​

❌ Mistake 1: Forgetting the +1 in Width Calculation​

❌ Mistake 2: Starting from Position 0​

❌ Mistake 3: Not Handling Null Nodes​

❌ Mistake 4: Creating New List Every Time​

Alternative Approach: Using int[]​

Testing the Solution​

The Aha Moment​

Key Takeaways​

The Broader Pattern​

Similar Problems​

The Core Pattern​

Conclusion​

Practice Problems​