TreeNode Class and Level-Order BFS
Construct binary trees from arrays, implement BFS with a deque to print level by level, and solve maximum-depth using BFS.
TreeNode Class and Level-Order BFS is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The TreeNode Class Foundation
A binary tree is a hierarchical data structure where each node has at most two children, called left and right. In Python, we model a node with a simple class: class TreeNode: def __init__(self, val=0, left=None, right=None). Every tree problem in interviews starts with this definition — you will see it in nearly every LeetCode tree problem's boilerplate.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a small tree manually:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)Building Trees from Arrays
Interview problems often give you a tree represented as a level-order array, where None marks missing nodes. Given index i, the left child is at 2i+1 and the right child at 2i+2. Writing a helper to deserialise this array into linked TreeNodes is a valuable utility that saves time during practice sessions.
from collections import deque
def build_tree(arr):
if not arr or arr[0] is None:
return None
root = TreeNode(arr[0])
q = deque([root])
i = 1
while q and i < len(arr):
node = q.popleft()
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
q.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
q.append(node.right)
i += 1
return root
root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)What is BFS and Why a Queue?
Breadth-First Search (BFS) visits all nodes at depth d before visiting any node at depth d+1. This level-by-level traversal is exactly what a queue (FIFO) gives us: we enqueue the root, then process nodes one at a time, enqueuing each node's children as we go. Python's collections.deque gives O(1) appendleft and popleft, making it the right choice over a plain list.
from collections import deque
def bfs_print(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root) # 1 2 3 4Level-Order BFS: Grouping by Level
The standard BFS variant groups nodes into levels by recording the queue size at the start of each iteration. Process exactly that many nodes, collect their values, then move to the next level. This produces a list of lists — a very common interview output format for problems like binary tree level-order traversal, zigzag traversal, and right side view.
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root)) # [[1], [2, 3], [4]]Maximum Depth via BFS
The maximum depth of a binary tree equals the number of levels in its BFS traversal. Simply count how many times you complete a level loop. This gives an O(n) time and O(w) space solution where w is the maximum width of the tree. For a balanced tree, w is O(n/2), so worst-case space is O(n).
from collections import deque
def max_depth_bfs(root):
if not root:
return 0
depth = 0
q = deque([root])
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depth
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root)) # 3Right Side View of a Binary Tree
The right side view returns the last node visible when you look at the tree from the right — i.e., the last element of each level in the BFS traversal. This is a direct application of level-order BFS: collect the final node in each level loop. Time complexity is O(n), space is O(w) for the queue.
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root)) # [1, 3, 5]Zigzag Level-Order Traversal
In zigzag traversal, odd levels are collected left-to-right and even levels right-to-left. The cleanest implementation keeps the BFS queue unchanged and simply reverses alternating level lists before appending to the result. Track the direction with a boolean flag that flips at each level. This avoids double-ended deque complexity in the inner loop.
from collections import deque
def zigzag_level_order(root):
if not root:
return []
result = []
q = deque([root])
left_to_right = True
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level if left_to_right else level[::-1])
left_to_right = not left_to_right
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))BFS Space Complexity Analysis
BFS uses O(w) space where w is the maximum width of the tree. For a perfect binary tree with n nodes, the last level has (n+1)/2 nodes — so BFS can hold up to n/2 nodes in the queue simultaneously. This makes BFS worse in space than DFS (O(h)) for wide balanced trees but better for deep-skewed trees where DFS call-stack depth equals n.
# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)
# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)
from collections import deque
def skewed_tree(n):
root = TreeNode(1)
cur = root
for i in range(2, n+1):
cur.right = TreeNode(i)
cur = cur.right
return root
root = skewed_tree(10)
print('BFS on skewed tree is safe')Average of Levels in Binary Tree
Computing the average value at each level is another direct BFS application. Sum all values at a level, divide by the count, and append to the result list. This problem tests that you can do arithmetic within the level loop. Always use float division in Python 3 (the / operator), and handle the empty-tree edge case at the start.
from collections import deque
def average_of_levels(root):
if not root:
return []
result = []
q = deque([root])
while q:
size = len(q)
total = 0
for _ in range(size):
node = q.popleft()
total += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(total / size)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root)) # [3.0, 14.5, 11.0]Minimum Depth via BFS
The minimum depth is the distance from root to the nearest leaf node (a node with no children). BFS finds this optimally: the first leaf node encountered during level-order traversal is guaranteed to be at the minimum depth. Return the current depth as soon as you hit a leaf. This is O(n) worst-case but often terminates much earlier for balanced trees.
from collections import deque
def min_depth(root):
if not root:
return 0
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
# A leaf has no children
if not node.left and not node.right:
return depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
return 0
root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5) # leaf at depth 2
print(min_depth(root)) # 2Connecting Level-Order Siblings
The populate next-right pointers problem asks you to link each node to its right neighbour at the same level. With BFS this is straightforward: within each level loop, set node.next = q[0] for all nodes except the last one. This is a classic example where BFS makes the solution obvious while DFS requires careful pointer tracking across subtrees.
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i < size - 1:
node.next = q[0]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
print('BFS connect: O(n) time, O(w) space')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: TreeNode class definition and how to build trees from arrays, level-order BFS using a deque with the level-size trick to group nodes, and applications including max depth, min depth, right-side view, zigzag traversal, and average-of-levels. Next up we explore recursive DFS traversal orders.
Frequently asked questions
Is the “TreeNode Class and Level-Order BFS” lesson free?
Yes — the full text of “TreeNode Class and Level-Order BFS” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “TreeNode Class and Level-Order BFS”?
Construct binary trees from arrays, implement BFS with a deque to print level by level, and solve maximum-depth using BFS. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “TreeNode Class and Level-Order BFS” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- TreeNode Class and Level-Order BFS
- In-Order, Pre-Order, Post-Order DFS
- Diameter, Height, and Balanced Trees
- Path Sum and Lowest Common Ancestor