DSA Interview Prep · Lesson

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.

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)

All lessons in this course

← Back to DSA Interview Prep