Abstract / Summary

Find the maximum distance between the leftmost and rightmost nodes at any level in a binary tree.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 46% (1+ million submissions).

Typical patterns to solve this problem:

• Binary Tree
• Breadth First Search
• Depth First Search
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided widthOfBinaryTree method computes the maximum width among all levels of a binary tree. Width is defined as the number of positions between the leftmost and rightmost non-null nodes on a level, inclusive of the end nodes. The algorithm performs a breadth-first traversal while assigning a virtual index to each node as if the tree were a complete binary tree. By tracking the smallest and largest indices at each depth, it derives the width for that level and retains the greatest value encountered.

Key Steps

Initialization

The algorithm starts by establishing a result variable that holds the best width found so far and a dictionary named todo that maps a virtual position to the corresponding node at the current level. The root node receives position 0.

result = 1
todo = {0: root}

Level-by-Level Traversal

A while loop drives the level order processing. It continues as long as there are nodes recorded in todo. At each iteration a fresh dictionary next is prepared to collect the children of the nodes currently being examined.

while todo:
    next = {}
    ...
    todo = next

Building the Mapping for the Next Level

Inside the loop, a for statement iterates over the positions stored in todo. For each position the algorithm extracts the associated node. If the node possesses a left child, that child is placed in next with an index equal to 2 * pos. If a right child exists, it is stored with index 2 * pos + 1. This arithmetic mirrors the indexing scheme of a complete binary tree, guaranteeing that gaps caused by missing nodes are reflected in the numeric distance between indices.

for pos in todo:
    node = todo[pos]
    if node.left:
        next[2 * pos] = node.left
    if node.right:
        next[2 * pos + 1] = node.right

Computing the Width of the Current Level

After the children have been collected, the algorithm determines the width of the current level. It does so by subtracting the smallest key in todo from the largest key, adding one to include both endpoints. This calculation automatically accounts for any absent nodes between the extremes because the virtual indices preserve the spacing that would exist in a full binary tree.

width = 1 + max(todo) - min(todo)

Updating the Global Maximum

The width just computed is compared with the running maximum stored in result. If the new width is larger, result is updated accordingly. This ensures that by the time the traversal finishes, result holds the greatest width observed across all levels.

result = max(result, width)

Completion

When the while loop exits-meaning there are no more nodes to process-the method returns the final result, which represents the maximum width of the binary tree.

return result

Edge Cases Handled

The implementation gracefully manages trees that are highly unbalanced or contain long chains of single-child nodes. Because each node receives a distinct virtual index based on its position in a hypothetical complete tree, the distance between the leftmost and rightmost nodes on any level correctly reflects the true width, even when many intermediate positions are empty. A tree consisting of only the root node is also covered: the initial result is set to 1, and the loop processes the single entry in todo, yielding a width of 1, which is then returned.

Sparse configurations where a level contains only a rightmost node (or only a leftmost node) are correctly measured because the min(todo) and max(todo) values will be identical, producing a width of 1 for that level. The algorithm therefore never underestimates width due to missing children.

Performance Optimizations

The code leverages a dictionary to store only the existing nodes at each depth, avoiding the allocation of placeholder entries for null children. This selective storage reduces memory consumption compared with approaches that enqueue None markers for absent nodes. The use of integer arithmetic for index calculation (2 * pos and 2 * pos + 1) is computationally cheap and eliminates the need for more complex data structures to track positions.

By recomputing max(todo) and min(todo) directly from the dictionary keys, the algorithm obtains the extreme indices without iterating over the node objects themselves, keeping the per-level overhead low. The overall design ensures that each node is visited exactly once, and the work performed per node is limited to constant-time dictionary operations and simple arithmetic, yielding an efficient traversal for large trees.

Imagine a giant family tree where every person has two children. Sometimes a person might have a child on the left, a child on the right, or both. This code helps figure out how wide each layer of the tree is by looking at how spread out the people in that layer are.

The code starts by putting the very first person in a list and giving them a special number of zero. It keeps track of everyone in the current row and gives each person a number based on their position. If a person is at position zero, their left child becomes number zero and their right child becomes number one. If the parent has a bigger number, the children simply double that number and add one if they are on the right side.

After counting everyone in the current row, the code looks at the smallest position number and the biggest position number to see the distance between them. This distance acts like a ruler to measure the width of that row. As the code finds each new row, it remembers the widest one seen so far. It keeps going until there are no more children in the tree to visit.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python							TS
	WalkCCC	C++	Java
	leetcode.ca	C++	Java	Python						Go
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fartem							Ruby
	fengvyi	C++
	fpdjsns	C++
	gouthampradhan		Java
	halfrost									Go
	haoel			Python
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007			Python
	ruoru						Rust
	suxrobGM					C#
	trung-hn			Python
	varunu28		Java
	vthwang		Java
	wisdompeak	C++
	yuanliu666								Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
gouthampradhan	Java
halfrost	Go
haoel	Python
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality