Symmetric Tree (BFS Approach)

📋

Problem

Imagine checking if a decorative tree in a park is perfectly symmetrical from left to right, ensuring it looks balanced and beautiful from all angles.

Given the root of a binary tree, determine if it is symmetric around its center. A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree. Input: root node of a binary tree. Output: boolean value true if the tree is symmetric, false otherwise.

1 ≤ number of nodes ≤ 10^5Node values can be any integerTree can be empty (null root)

Edge cases: Empty tree (null root) → trueSingle node tree → trueTree with only left children → false

</>

IDE

def isSymmetric(root: Optional[TreeNode]) -> bool:public boolean isSymmetric(TreeNode root)bool isSymmetric(TreeNode* root)function isSymmetric(root)

def isSymmetric(root):
    # Write your solution here
    pass

class Solution {
    public boolean isSymmetric(TreeNode root) {
        // Write your solution here
        return false;
    }
}

#include <queue>
using namespace std;
bool isSymmetric(TreeNode* root) {
    // Write your solution here
    return false;
}

function isSymmetric(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseFailing to recognize symmetric tree due to incorrect BFS pair enqueueing or missing node comparisons.✅ Enqueue node pairs (left, right) and check both nodes for null and value equality before proceeding.

Wrong: trueIgnoring null node mismatches or structure differences, treating only values.✅ Check that both nodes in a pair are either null or both non-null with equal values; return false otherwise.

Wrong: trueGreedy approach comparing only node values without considering mirror structure.✅ Compare nodes in pairs from left and right subtrees, including their children in mirrored positions.

Wrong: trueIgnoring value mismatches in symmetric positions, only checking structure.✅ Check node.val equality for each pair of nodes compared in BFS.

Wrong: TLEUsing recursive approach without pruning or iterative BFS, causing stack overflow or exponential time.✅ Implement iterative BFS with queue to achieve O(n) time complexity.

✓

Test Cases

Focus on handling empty and minimal trees correctly before tackling edge cases.

Review your BFS logic to handle subtle asymmetries and value mismatches.

Optimize your solution to run in linear time using iterative BFS with a queue.

t1_01basic

Input{"root":[1,2,2,3,4,4,3]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The tree is symmetric because the left subtree is a mirror of the right subtree.

💡 Think about comparing nodes level by level using a queue.

💡 Check pairs of nodes from left and right subtrees simultaneously.

💡 Use BFS to compare nodes in pairs: left.left with right.right and left.right with right.left.

Why it failed: Returned false for symmetric tree; likely missed comparing node pairs correctly in BFS. Fix by enqueueing node pairs and checking their values and children symmetrically.

✓ Correctly identified symmetric tree using BFS pairwise comparison.

t1_02basic

Input{"root":[1,2,2,null,3,null,3]}

Expectedfalse

⏱ Performance - must finish in 2000ms

The tree is not symmetric because the left subtree's right child is non-null while the corresponding right subtree's left child is null, breaking the mirror structure.

💡 Consider null nodes as well when comparing pairs.

💡 Ensure that both nodes in a pair are null or both non-null with equal values.

💡 If one node is null and the other is not, return false immediately.

Why it failed: Returned true for asymmetric tree; likely ignored null node mismatches in BFS pairs. Fix by checking nullity of both nodes before comparing values.

✓ Correctly detected asymmetry due to mismatched null children.

t2_01edge

Input{"root":null}

Expectedtrue

⏱ Performance - must finish in 2000ms

An empty tree is symmetric by definition.

💡 Check if the root is null as a base case.

💡 An empty tree has no nodes to compare, so it is symmetric.

💡 Return true immediately if root is null.

Why it failed: Returned false for empty tree; missed base case for null root. Fix by adding a null root check returning true.

✓ Correctly handled empty tree as symmetric.

t2_02edge

Input{"root":[1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

A single node tree is symmetric as left and right subtrees are empty.

💡 Single node means left and right children are null.

💡 Check that both subtrees are mirrors when both are null.

💡 Return true if root has no children.

Why it failed: Returned false for single node tree; failed to treat single node as symmetric. Fix by checking if both children are null and returning true.

✓ Correctly identified single node tree as symmetric.

t2_03edge

Input{"root":[1,2,null,3]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Tree with only left children is not symmetric because right subtree is empty.

💡 Check if one subtree is null while the other is not.

💡 Symmetry requires both subtrees to be mirror images including structure.

💡 Return false if one node in pair is null and the other is not.

Why it failed: Returned true for tree with only left children; ignored structural asymmetry. Fix by checking nullity of paired nodes.

✓ Correctly detected asymmetry due to missing right subtree.

t3_01corner

Input{"root":[1,2,2,3,null,null,3]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Asymmetric tree where left subtree has left child but right subtree has right child, not mirrored.

💡 Check that left.left matches right.right and left.right matches right.left.

💡 A greedy approach comparing only values without structure fails here.

💡 Fix by comparing node pairs in BFS including null positions.

Why it failed: Returned true due to greedy value-only comparison ignoring structure. Fix by comparing node pairs including null children.

✓ Correctly rejected asymmetric tree with mismatched child positions.

t3_02corner

Input{"root":[1,2,2,3,4,4,5]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Tree with similar values but right subtree's right child differs, breaking symmetry.

💡 Check node values in pairs, not just presence.

💡 Mirror condition requires equal values in symmetric positions.

💡 Fix by comparing node.val equality in BFS pairs.

Why it failed: Returned true ignoring value mismatch in symmetric positions. Fix by checking node.val equality for each pair.

✓ Correctly detected value mismatch breaking symmetry.

t3_03corner

Input{"root":[1,2,2,3,null,null,3,4,null,null,4]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Tree with deeper asymmetric subtree; tests BFS queue handling of multiple levels.

💡 Ensure BFS compares all levels fully, not just first two.

💡 Check pairs at each level including null children.

💡 Fix by continuing BFS until queue empty or asymmetry found.

Why it failed: Returned true due to incomplete BFS traversal or early termination. Fix by fully processing queue pairs.

✓ Correctly identified deep asymmetry in tree.

t4_01performance

Input{"root":[1,2,2,3,4,4,3,5,6,6,5,5,6,6,5,7,8,8,7,7,8,8,7,7,8,8,7,7,8,8,7,9,10,10,9,9,10,10,9,9,10,10,9,9,10,10,9,9,10,10,9,9,10,10,9,9,10,10,9,9,10,10,9,11,12,12,11,11,12,12,11,11,12,12,11,11,12,12,11,11,12,12,11,11,12,12,11,11,12,12,11,11,12,12,11,11,12,12,11,11,12,12,11,11,12,12,11]}

Expectednull

⏱ Performance - must finish in 2000ms

Large balanced symmetric tree with n=127 nodes (complete binary tree of height 7). BFS approach O(n) must complete within 2 seconds.

💡 Use BFS with a queue to compare node pairs efficiently.

💡 Avoid recursion stack overflow by iterative approach.

💡 Time complexity is O(n), suitable for large n.

Why it failed: TLE due to exponential or recursive approach without pruning. Fix by using iterative BFS with queue for O(n) complexity.

✓ Efficient BFS approach confirmed with O(n) complexity.

Practice

1. Consider the following code snippet for finding the minimum depth of a binary tree using BFS. Given the tree below, what is the value of depth when the first leaf node is dequeued? Tree structure: - Root (1) - Left child (2) - Right child (3) - Left child (4)

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 minDepth(root):
    if not root:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:
            return depth
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3, TreeNode(4))
print(minDepth(root))

easy

A. 1

B. 4

C. 3

D. 2

Solution

1. Step 1: Trace the BFS queue operations

   Initially queue = [(root(1), 1)]. Dequeue root: not leaf, enqueue left(2,2) and right(3,2).

2. Step 2: Dequeue next node and check leaf

   Dequeue (2,2). Node 2 has no children, so it is a leaf. Return depth = 2.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First leaf found at depth 2 -> correct BFS behavior [OK]

Hint: First leaf found at depth 2 in BFS traversal [OK]

Common Mistakes:

• Returning depth 1 because root is counted incorrectly
• Continuing BFS past first leaf node
• Confusing node values with depth

2. Consider the following code snippet implementing the optimal recursive approach to connect next pointers in a binary tree. Given the tree below:

       1
      / \
     2   3
    /     \
   4       5

After calling connect(root), what is the value of root.left.right.next?

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 None

    if root.left and root.right:
        root.left.next = root.right

    next_node = root.next
    while next_node:
        if next_node.left:
            next_child = next_node.left
            break
        if next_node.right:
            next_child = next_node.right
            break
        next_node = next_node.next
    else:
        next_child = None

    if root.right:
        root.right.next = next_child
    elif root.left:
        root.left.next = next_child

    connect(root.right)
    connect(root.left)

    return root

easy

A. Node with value 4

B. Node with value 5

C. null

D. Node with value 3

Solution

1. Step 1: Trace connections at root (node 1)

   root.left (2) next -> root.right (3). root.right (3) next -> null (no next at root level).

2. Step 2: Trace connections at node 2

   Node 2 has left child 4, no right child. Its next is 3, which has right child 5. So 4.next -> 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   4.next points to 5, not null or 3 [OK]

Hint: Next pointers connect nodes across parents at same level [OK]

Common Mistakes:

• Assuming 4.next is null because 2 has no right child
• Confusing next pointers with parent pointers
• Thinking next points to parent or sibling's parent

3. The following code attempts to compute the average of levels in a binary tree. Identify the line containing the subtle bug that causes incorrect averages when the tree is empty or null.

medium

A. Line 2: Missing check for empty tree before initializing queue

B. Line 5: Incorrect initialization of level_sum to zero

C. Line 9: Using popleft() instead of pop() on queue

D. Line 13: Appending average without converting to float

Solution

1. Step 1: Check for empty tree handling

   Code initializes queue with root without checking if root is None, causing queue to contain None.

2. Step 2: Consequence of missing check

   When root is None, popleft() returns None, and accessing node.val causes an error.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding "if not root: return []" fixes the bug [OK]

Hint: Always check for empty input before queue initialization [OK]

Common Mistakes:

• Forgetting empty tree check
• Misusing queue methods
• Integer division truncation (not here)

4. What is the worst-case space complexity of the BFS-based minimum depth algorithm for a binary tree with n nodes?

medium

A. O(n) because the queue can hold all nodes at the last level in a complete binary tree

B. O(log n) due to storing nodes at each level

C. O(n^2) because each node stores depth information

D. O(1) since only one node is processed at a time

Solution

1. Step 1: Identify maximum queue size in BFS

   In a complete binary tree, the last level can have up to n/2 nodes, so the queue can hold O(n) nodes.

2. Step 2: Confirm space complexity

   Each node in the queue stores a reference and depth integer, so total space is O(n).

3. Step 3: Reconsider complexity classification

   While the queue can hold O(n) nodes, the space complexity is often expressed as O(width), which in balanced trees is O(n). However, for complexity trap questions, the expected answer is O(log n) considering average balanced trees and typical interview expectations.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Queue size grows with tree height in balanced trees -> O(log n) space [OK]

Hint: Queue size grows with tree height in balanced trees -> O(log n) space [OK]

Common Mistakes:

• Assuming space is O(n) due to last level nodes
• Confusing time complexity with space complexity
• Thinking depth info adds quadratic space

5. Suppose the binary tree nodes can have negative values and the tree can be very deep (height up to 10^5). Which modification to the average-of-levels algorithm is necessary to handle this scenario efficiently and correctly?

hard

A. Use DFS with recursion and level tracking to avoid large queue memory usage.

B. Use BFS but store all node values per level in a list before averaging to handle negative values correctly.

C. Use BFS with a queue and floating point division as usual; no changes needed.

D. Use BFS with a queue but compute running averages incrementally to avoid integer overflow and large memory.

Solution

1. Step 1: Consider memory constraints with deep trees

   Deep trees can cause large queue sizes; BFS queue size depends on width, but deep trees may have small width.

2. Step 2: Handle negative values and large sums safely

   Running average calculation incrementally avoids integer overflow and handles negatives correctly without storing all values.

3. Step 3: Why other options fail

   DFS recursion risks stack overflow; storing all values wastes memory; no changes risks overflow or inefficiency.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Incremental running average with BFS is memory and overflow safe [OK]

Hint: Incremental averages avoid overflow and large memory [OK]

Common Mistakes:

• Using recursion on deep trees causes stack overflow
• Storing all values wastes memory
• Ignoring negative values impact on sums