Keys to solutions
- Level order traversal → Breadth first search (BFS)
- Specific to maximum width computation, a sequential indexing starting from the root node and following the level order traversal order makes it easier to keep track of the width of each level
Basic data structure setup for binary tree
We start with a TreeNode class that allows us to create a node for a binary tree that can store a value and have references to its left and right children:
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = rightBFS implementation with python’s deque
Basic “dequeue node enqueue children” pattern at each level
For BFS, we want to use a queue to store nodes at the level we will traverse. The “first in, first out” (FIFO) characteristic of queue is best implemented with python’s deque (doubly ended queue) descriptively (for a refresher of deque, see this article here).
At each level, the “dequeue the node, enqueue the children” pattern looks like the following:
# Dequeue node
node = queue.popleft()
# Enqueue left child if not empty
if node.left:
queue.append(node.left)
# Enqueue right child if not empty
if node.right:
queue.append(node.right)Indexing sequence for per-level width computation
To avoid having to also keep track of the level index itself, the simplest way for us to index is to take a zero-based sequence that starts at the root node and increments from left to right and level by level.
How to get the width of each level?
With this indexing system (Figure 1), we can see that the width of each level is rightmost non-null node index — leftmost non-null node index + 1:
- level 1 width = 1
- level 2 width = 2–1 + 1 = 2
- level 3 width = 6–3 + 1 = 4
How does each node’s index relate to their children’s indices?
In Figure 2, we can see that with our indexing system, each parent-children group (as highlighted in green) could be:
- Given node index
idx - Index of its left child =
2 * idx + 1 - Index of its right child =
2 * idx + 2
Python implementation
Put these together, we use a deque to store both tree nodes and their indices at each level.
Before working on (node, idx)s of each level, we first keep a note of the first non-null idx as leftmost_idx . As we complete traversing the level, the latest idx would be the rightmost non-null node’s index at the level. This gives us the width of each level as idx — leftmost_idx + 1 . This then allows us to obtain the maximum width across all levels when we complete the traversal:
from collections import deque
from typing import Optional
# Define a binary tree node
class TreeNode(object):
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:
# If tree is empty, return 0
if not root:
return 0
# Initialize maximum width with 0
max_width = 0
# Initialize a queue for BFS.
# For each node, we store both the node and its index.
queue = deque([(root, 0)])
# At beginning of each loop,
# the FIFO queue only contains all nodes at the current level
# Ii a left-to-right order
while queue:
level_length = len(queue)
# We first keep a note of the leftmost non-null node's index
_, level_start_index = queue[0]
# Now we follow the "dequeue node, enqueue children" pattern
# to (1) work on the node of the current level and
# (2) populate the queue with nodes of the next level
for _ in range(level_length):
# As we traverse the current level, we dequeue the node
node, idx = queue.popleft()
# If left child exists, we enqueue it
if node.left:
# Left child's index is 2 * parent's index + 1
queue.append((node.left, 2 * idx + 1))
# If right child exists, we enqueue it
if node.right:
# Right child's index is 2 * parent's index + 2
queue.append((node.right, 2 * idx + 2))
# At the end of each level traversal, we update the maximum width
max_width = max(max_width, idx - level_start_index + 1)
return max_widthTime and space complexity
- Space complexity = O(n): At most, the queue will hold all the nodes at the level of the tree that has the maximum width. In the worst case, this could be the last level of a balanced binary tree containing approximately n/2 nodes → O(n/2) = O(n)
- Time complexity = O(n): Since we need to traverse all nodes in the tree once
where n = number of nodes in the tree
Example unit tests (pytest)
import pytest
from leetcode_journal.bfs.binary_tree_maximum_width_662_medium import (
Solution,
TreeNode,
)
@pytest.fixture
def simple_tree():
"""
Constructs a 3-level, max-with = 4 binary tree as follows:
1
/ \
2 3
/ \ \
4 5 6
"""
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)
node2 = TreeNode(2, left=node4, right=node5)
node3 = TreeNode(3, left=None, right=node6)
root = TreeNode(1, left=node2, right=node3)
return root
@pytest.fixture
def single_node_tree():
return TreeNode(1)
@pytest.fixture
def empty_tree():
return None
def test_max_width_of_simple_tree(simple_tree):
solution = Solution()
assert solution.widthOfBinaryTree(simple_tree) == 4
def test_max_width_of_single_node_tree(single_node_tree):
solution = Solution()
assert solution.widthOfBinaryTree(single_node_tree) == 1
def test_max_width_of_empty_tree(empty_tree):
solution = Solution()
assert solution.widthOfBinaryTree(empty_tree) == 0