Symmetric Tree (BFS Approach)

▶

Steps

setup

Check if root is null

The algorithm first checks if the root node is null. Since the root exists, it proceeds to initialize the queue.

💡 If the root is null, the tree is symmetric by definition, so this check quickly handles empty trees.

Line:

if not root:
    return True

💡 This step establishes the base case for an empty tree.

setup

Initialize queue with root twice

The queue is initialized with two references to the root node to start comparing the tree with itself.

💡 Adding the root twice sets up the BFS to compare left and right subtrees in pairs.

Line:

queue = deque([root, root])

💡 This step prepares the queue for BFS pairwise comparison.

traverse

Dequeue first pair of nodes (root, root)

The algorithm dequeues two nodes from the queue: both are the root node with value 1.

💡 Dequeuing pairs allows the algorithm to compare corresponding nodes in the left and right subtrees.

Line:

t1 = queue.popleft()
t2 = queue.popleft()

💡 This step shows the start of the BFS comparison at the root level.

compare

Check if both nodes are null

Both dequeued nodes are not null, so the algorithm proceeds to the next checks.

💡 If both nodes were null, it would mean symmetric empty branches, so the algorithm would continue without enqueueing children.

Line:

if not t1 and not t2:
    continue

💡 This step confirms that the nodes exist and need to be compared.

compare

Check if one node is null or values differ

Both nodes have value 1, so the algorithm continues to check their children for symmetry.

💡 If values differ or one node is null, the tree is not symmetric and the algorithm returns false immediately.

Line:

if not t1 or not t2:
    return False
if t1.val != t2.val:
    return False

💡 This step confirms the root nodes match, so symmetry depends on children.

compare

Check if left child of t1 and right child of t2 mismatch in nullity

The algorithm checks if one of t1.left or t2.right is null while the other is not. Both exist, so it continues.

💡 This early termination check quickly detects asymmetry in child structure.

Line:

if (t1.left is None) != (t2.right is None):
    return False

💡 This step ensures the left subtree of t1 mirrors the right subtree of t2 structurally.

compare

Check if right child of t1 and left child of t2 mismatch in nullity

The algorithm checks if one of t1.right or t2.left is null while the other is not. Both exist, so it continues.

💡 This check complements the previous one to ensure full mirror structure.

Line:

if (t1.right is None) != (t2.left is None):
    return False

💡 This step confirms the right subtree of t1 mirrors the left subtree of t2 structurally.

expand

Enqueue children pairs for next comparisons

The algorithm enqueues the left child of t1 and right child of t2, then the right child of t1 and left child of t2.

💡 Enqueuing children pairs in this mirrored order is key to BFS symmetry checking.

Line:

queue.append(t1.left)
queue.append(t2.right)
queue.append(t1.right)
queue.append(t2.left)

💡 This step sets up the next level of node comparisons in the BFS queue.

traverse

Dequeue next pair (2,7) and compare values

The algorithm dequeues nodes with values 2 and 3. Since values differ, it will continue checking other pairs as the tree is symmetric.

💡 Comparing node values at each pair is essential to detect asymmetry.

Line:

t1 = queue.popleft()
t2 = queue.popleft()
if t1.val != t2.val:
    return False

💡 This step shows the BFS comparison at the next level confirming symmetry.

reconstruct

Return true after all pairs checked

Since the example tree is symmetric, the algorithm would have continued checking all pairs and finally returned true.

💡 If no asymmetry is found during BFS, the tree is symmetric.

Line:

return True

💡 This final step confirms the tree's symmetry after exhaustive BFS checks.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSymmetric(root):
    # STEP 1: Check if root is null
    if not root:
        return True
    # STEP 2: Initialize queue with root twice
    queue = deque([root, root])
    while queue:
        # STEP 3: Dequeue two nodes
        t1 = queue.popleft()
        t2 = queue.popleft()
        # STEP 4: If both null, continue
        if not t1 and not t2:
            continue
        # STEP 5: If one null or values differ, return False
        if not t1 or not t2:
            return False
        if t1.val != t2.val:
            return False
        # STEP 6: Early termination checks
        if (t1.left is None) != (t2.right is None):
            return False
        if (t1.right is None) != (t2.left is None):
            return False
        # STEP 8: Enqueue children pairs
        queue.append(t1.left)
        queue.append(t2.right)
        queue.append(t1.right)
        queue.append(t2.left)
    # STEP 10: Return True if all pairs pass
    return True

📊

Symmetric Tree (BFS Approach) - Watch the Algorithm Execute, Step by Step

Watching the BFS approach step-by-step reveals how pairs of nodes are compared and how early termination prevents unnecessary work.

1223443

Current node: 1

1223443

DFS Stack

1 (entered)queue=[1,1]

Current node: 1

1223443

DFS Stack

1 (left_done)t1=1 t2=1 queue=[]

Current node: 1

1223443

DFS Stack

1 (right_done)t1=1 t2=1

Current node: 1

1223443

DFS Stack

1 (returning)t1=1 t2=1

Current node: 1

1223443

DFS Stack

1 (returning)t1=1 t2=1

Current node: 1

1223443

DFS Stack

1 (returning)t1=1 t2=1

1223443

DFS Stack

1 (returning)queue=[2,7,3,4]

Current node: 2

1223443

DFS Stack

1 (returning)t1=2 t2=7

1223443

Return: true

Key Takeaways

✓ The BFS approach compares nodes in pairs to check symmetry level by level.

This insight is hard to see from code alone because the queue operations and pairwise comparisons are implicit.

✓ Early termination checks on child nullity prevent unnecessary traversal.

Understanding these checks visually shows how the algorithm quickly detects asymmetry.

✓ Enqueuing children in mirrored order is crucial for correct BFS symmetry checking.

The visualization clarifies why the order of enqueueing matters for comparing mirrored nodes.

Practice

1. You need to collect nodes of a binary tree grouped by their depth level, from top to bottom, left to right. Which algorithmic approach guarantees an optimal solution that visits each node exactly once and groups nodes by their level?

easy

A. Use a Depth-First Search (DFS) without tracking levels, then sort nodes by depth after traversal.

B. Use a recursive approach that collects nodes in preorder traversal order.

C. Use Breadth-First Search (BFS) with a queue to process nodes level by level.

D. Use a greedy approach that picks the leftmost node at each level before moving to the next.

Solution

1. Step 1: Understand the problem requirement

   The problem requires grouping nodes by their depth level, visiting nodes level by level from top to bottom and left to right.

2. Step 2: Evaluate algorithm suitability

   BFS with a queue naturally processes nodes level by level, ensuring each node is visited once and grouped correctly. DFS without level tracking or greedy approaches do not guarantee correct grouping or order.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   BFS processes nodes in level order by design [OK]

Hint: BFS naturally processes nodes level by level [OK]

Common Mistakes:

• Thinking DFS without level tracking groups nodes by level
• Assuming greedy leftmost picks produce level order
• Sorting after DFS is inefficient

2. You are given a binary tree and need to find the shortest distance from the root node down to the nearest leaf node. Which algorithmic approach guarantees the optimal solution with minimal time complexity?

easy

A. Breadth-First Search (BFS) stopping at the first encountered leaf node

B. Dynamic Programming storing minimum depths for subtrees and combining results

C. Depth-First Search (DFS) exploring all paths to leaves and returning the minimum depth

D. Greedy approach choosing the child with the smaller value at each step

Solution

1. Step 1: Understand the problem requirement

   The problem asks for the minimum depth to a leaf node, which means the shortest path from root to any leaf.

2. Step 2: Identify the algorithm that finds shortest path in unweighted trees

   BFS explores nodes level by level and stops immediately when it finds the first leaf, ensuring the shortest path is found efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS stops at first leaf -> minimal depth found [OK]

Hint: Shortest path in trees -> BFS with early stop [OK]

Common Mistakes:

• Assuming DFS always finds minimum depth efficiently
• Confusing greedy value-based choice with shortest path
• Thinking DP is needed for simple tree traversal

3. What is the space complexity of the optimal BFS approach for computing the average of levels in a binary tree, where n is the number of nodes and w is the maximum width of the tree?

medium

A. O(log n) because the tree height bounds the queue size

B. O(n) because all nodes are stored in the queue at once

C. O(w) because the queue holds at most all nodes at the widest level

D. O(n) due to storing all node values in the result list

Solution

1. Step 1: Identify maximum queue size during BFS

   The queue holds nodes level-by-level; max size is the maximum number of nodes at any level, i.e., width w.

2. Step 2: Consider auxiliary space for result list

   Result list stores one average per level, at most height h, which is ≤ n but smaller than w in wide trees.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Queue size dominates space, bounded by maximum width w [OK]

Hint: Queue size = max nodes at any level = width w [OK]

Common Mistakes:

• Assuming queue holds all nodes simultaneously (O(n))
• Confusing height with width for queue size
• Ignoring space for result list

4. The following code attempts to count good nodes in a binary tree using iterative DFS. Identify the line containing the subtle bug that causes incorrect counting.

medium

A. Line checking if node.val > max_val instead of >= max_val

B. Line updating max_val with max(max_val, node.val)

C. Line pushing node.right onto the stack

D. Line returning count at the end

Solution

1. Step 1: Examine condition for counting good nodes

   The condition uses strictly greater (node.val > max_val), but problem definition includes equality (>=).

2. Step 2: Understand impact of strict inequality

   This causes undercounting when node.val equals max_val, missing some good nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing > to >= fixes counting [OK]

Hint: Check if condition uses >= not > for counting [OK]

Common Mistakes:

• Using > instead of >=
• Not updating max_val before pushing children
• Ignoring null root case

5. What is the space complexity of the optimal approach that uses next pointers to traverse levels when populating next right pointers in a perfect binary tree with n nodes?

medium

A. O(1) because it uses existing next pointers without extra data structures

B. O(n) due to the queue used for level order traversal

C. O(log n) due to recursion stack in a DFS approach

D. O(n) because each node stores a next pointer

Solution

1. Step 1: Identify data structures used in the optimal approach

   The approach uses no extra queue or recursion; it uses existing next pointers to traverse levels.

2. Step 2: Analyze space usage

   Only constant extra variables like pointers are used, so space complexity is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No extra data structures or recursion stack used [OK]

Hint: Optimal approach uses constant extra space [OK]

Common Mistakes:

• Confusing with BFS queue space
• Assuming recursion is used
• Counting next pointer storage as extra space