Symmetric Tree (DFS Approach)

📋

Problem

Imagine you want to verify if a decorative tree in your garden is perfectly symmetrical, like a mirror image on both sides.

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). Return true if the tree is symmetric, and false otherwise.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers and can be positive, negative, or zero.

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 <vector>
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: falseReturning false for empty tree (null root) instead of true.✅ Add a base case: if root is null, return true immediately.

Wrong: trueNot checking for null subtree mismatches, causing false positives when one subtree is null and the other is not.✅ Before comparing node values, check if both nodes are null or both non-null; return false if mismatch.

Wrong: falseMixing up left and right pointers in recursive mirror calls.✅ In isMirror, call isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left), not t2.left with t1.left.

Wrong: trueGreedy approach checking only root children without full recursion.✅ Recursively check all subtree pairs for mirror symmetry, not just immediate children.

Wrong: TLEUsing exponential or repeated subtree traversals instead of O(n) DFS.✅ Implement a single DFS traversal with early exit on mismatch to achieve O(n) time complexity.

✓

Test Cases

Try testing your code on empty and single node trees to handle base cases.

Focus on pointer swapping and structure checks to catch subtle symmetry bugs.

Optimize your recursion to run in linear time and avoid redundant checks.

t1_01basic

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

Expectedtrue

⏱ Performance - must finish in 2000ms

The left subtree is a mirror reflection of the right subtree.

💡 Check if left and right subtrees are mirror images recursively.

💡 Use a helper function to compare nodes in a mirrored manner.

💡 Return true only if node values match and subtrees are mirrors.

Why it failed: Incorrect output means the mirror comparison logic is flawed; ensure you compare left.left with right.right and left.right with right.left.

✓ Correctly identifies symmetric trees using mirror recursion.

t1_02basic

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

Expectedfalse

⏱ Performance - must finish in 2000ms

The left subtree has a right child 3, but the right subtree has a right child 3 instead of left, breaking symmetry.

💡 Check if null children are handled correctly in mirror comparison.

💡 Ensure both subtrees have matching structure and values in mirrored positions.

💡 Return false if one subtree has a child where the other does not.

Why it failed: Failing to check for null mismatches causes false positives; fix by verifying both nodes are null or both non-null before comparing values.

✓ Correctly detects asymmetry due to structural mismatch.

t2_01edge

Input{"root":null}

Expectedtrue

⏱ Performance - must finish in 2000ms

An empty tree is symmetric by definition.

💡 Consider the base case when the root is null.

💡 An empty tree has no nodes to violate symmetry.

💡 Return true immediately if root is null.

Why it failed: Returning false for null root misses the empty tree base case; fix by returning true if root is null.

✓ Handles empty tree correctly 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.

💡 Check if single node trees return true.

💡 Left and right children are null, so symmetric.

💡 Return true if root has no children.

Why it failed: Failing to handle single node trees causes incorrect false; fix by returning true if both children are null.

✓ Correctly identifies 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 as right subtree is empty.

💡 Check if asymmetry due to missing right subtree is detected.

💡 Compare null right subtree with non-null left subtree.

💡 Return false if one subtree is null and the other is not.

Why it failed: Not checking for null subtree mismatches causes false positives; fix by verifying both subtrees are null or non-null before value comparison.

✓ Correctly detects asymmetry in left-only child tree.

t3_01corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Symmetric tree where left.left and right.right have same values, testing correct mirror pointer usage.

💡 Beware of swapping left and right pointers incorrectly.

💡 Ensure isMirror compares left.left with right.right and left.right with right.left.

💡 Fix pointer usage if comparing left.left with right.left or right.right with left.right.

Why it failed: Mixing up pointers in mirror comparison causes false negatives; fix by swapping right subtree pointers in recursive calls.

✓ Correctly uses mirrored pointers in recursion.

t3_02corner

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Tree with same values but asymmetric structure, testing structure vs value confusion.

💡 Check both structure and values, not just values.

💡 Ensure null children are compared properly.

💡 Return false if structure differs even if values match.

Why it failed: Ignoring structure and only comparing values causes false positives; fix by checking nullity of children before value comparison.

✓ Correctly distinguishes structure asymmetry despite value similarity.

t3_03corner

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Greedy approach trap: tree looks symmetric at root but subtrees differ, testing full recursion necessity.

💡 Avoid greedy checks only at root level.

💡 Recursively verify all subtree pairs for symmetry.

💡 Return false if any subtree pair is not mirror.

Why it failed: Greedy approach checking only root children causes false positives; fix by full recursive mirror checks on all subtree pairs.

✓ Correctly applies full recursion to detect asymmetry.

t4_01performance

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

Expectednull

⏱ Performance - must finish in 2000ms

Large balanced tree with n=15 nodes (representative of large input), O(n) time complexity must complete within 2s.

💡 Use O(n) DFS traversal to check symmetry.

💡 Avoid redundant subtree comparisons.

💡 Early exit on mismatch to optimize performance.

Why it failed: Algorithm exceeding time limit likely uses exponential or repeated subtree checks; fix by using O(n) DFS with memoization or early exit.

✓ Algorithm runs in O(n) time confirming efficient DFS approach.

Practice

1. Given the following iterative postorder traversal code, what is the final output when run on the tree: root = TreeNode(1, None, TreeNode(2, TreeNode(3)))?

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited != peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

easy

A. [2, 3, 1]

B. [1, 3, 2]

C. [3, 2, 1]

D. [3, 1, 2]

Solution

1. Step 1: Trace traversal on given tree

   Start at root(1), go left (None), push 1. Then peek 1, right child is 2, move to 2, push 2, go left to 3, push 3, left None.

2. Step 2: Process nodes in postorder

   3 has no children, append 3. Back to 2, right visited, append 2. Back to 1, right visited, append 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches postorder [3, 2, 1] [OK]

Hint: Postorder output for this tree is [3,2,1] [OK]

Common Mistakes:

• Confusing order of appending nodes
• Off-by-one in stack popping

2. Given the following code for inverting a binary tree, what is the value of the left child of the root node after calling invertTree(root) on the tree below? Tree structure before inversion:

    2
   / \
  1   3

easy

A. 3

B. 1

C. 2

D. null

Solution

1. Step 1: Trace recursive calls on root=2

   invertTree called on left child (1) and right child (3), both leaves, so their children are null and return immediately.

2. Step 2: Swap left and right children of root=2

   After recursion, root.left and root.right are swapped: left becomes 3, right becomes 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root's left child after inversion is original right child 3 [OK]

Hint: Swapping children after recursion flips subtree positions [OK]

Common Mistakes:

• Confusing left and right child values after inversion
• Forgetting to swap after recursive calls
• Assuming root value changes

3. What is the space complexity of the optimal recursive approach to invert a binary tree, assuming the tree has n nodes and height h?

medium

A. O(n) because each node's children pointers are swapped individually

B. O(n) due to storing all nodes in a queue during traversal

C. O(1) because inversion is done in-place without extra data structures

D. O(h) due to recursion stack depth proportional to tree height

Solution

1. Step 1: Identify auxiliary space usage in recursion

   The algorithm uses recursion, so the call stack depth is proportional to the height h of the tree.

2. Step 2: Distinguish between in-place operations and recursion stack

   Swapping pointers is in-place (O(1) per node), but recursion stack space is O(h), not O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursion stack dominates space, proportional to tree height h [OK]

Hint: Recursion stack space depends on tree height, not node count [OK]

Common Mistakes:

• Confusing in-place operation with O(1) total space
• Assuming queue-based BFS space applies to recursive DFS
• Counting node swaps as extra space

4. What is the space complexity of the Morris Preorder Traversal approach for summing root-to-leaf numbers in a binary tree with n nodes?

medium

A. O(1) because Morris traversal uses threaded binary tree links without extra stack

B. O(n) due to recursion stack in DFS

C. O(h) where h is tree height due to implicit stack usage

D. O(n) because all nodes are visited and stored temporarily

Solution

1. Step 1: Identify space usage in Morris traversal

   Morris traversal modifies tree pointers temporarily to avoid recursion or explicit stack, so no extra stack space is used.

2. Step 2: Confirm no auxiliary data structures

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

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Morris traversal is known for O(1) space by threading tree [OK]

Hint: Morris traversal avoids recursion and stack [OK]

Common Mistakes:

• Confusing recursion stack with Morris traversal
• Assuming O(h) due to tree height

5. Suppose the problem is modified so that the tree can have nodes with arbitrary large depth, and you want to avoid recursion stack overflow. Which approach is best to check if the tree is balanced efficiently?

hard

A. Use the brute force recursive height check since it is simpler to implement.

B. Use iterative postorder traversal with a stack to compute heights and check balance.

C. Use a breadth-first traversal and check balance at each level.

D. Use a global variable to store height and recurse with tail recursion optimization.

Solution

1. Step 1: Understand recursion stack limitations

   Deep trees can cause recursion stack overflow in recursive solutions.

2. Step 2: Identify iterative approach benefits

   Iterative postorder traversal uses explicit stack, avoiding recursion limits and still computes heights and balance in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Iterative approach avoids recursion depth issues [OK]

Hint: Iterative traversal avoids recursion stack overflow [OK]

Common Mistakes:

• Assuming recursion with tail call optimization works in Python
• Using BFS which does not check subtree height balance
• Choosing brute force recursion despite stack limits