Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoftGoogle

Symmetric Tree (DFS Approach)

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"root":[1,2,2,3,4,4,3]}
Expectedtrue

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

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

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

t2_01edge
Input{"root":null}
Expectedtrue

An empty tree is symmetric by definition.

t2_02edge
Input{"root":[1]}
Expectedtrue

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

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

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

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

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

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

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

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

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

t4_01performance
Input{"root":[1,2,2,3,6,6,3,4,5,null,null,null,null,5,4]}
⏱ Performance - must finish in 2000ms

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

Practice

(1/5)
1. You are given a binary tree and a target sum. You need to determine if there exists a root-to-leaf path such that adding up all the values along the path equals the target sum. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Depth-first search (DFS) with early stopping upon finding a valid path
B. Greedy traversal choosing the child with the closest value to the target sum
C. Dynamic programming with memoization of partial sums at each node
D. Breadth-first search (BFS) exploring all paths level by level

Solution

  1. Step 1: Understand the problem constraints

    The problem requires checking if any root-to-leaf path sums to the target. This naturally fits a tree traversal pattern.
  2. Step 2: Identify the best approach

    DFS with early stopping is optimal because it explores paths deeply and stops as soon as a valid path is found, avoiding unnecessary work.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    DFS explores paths fully and stops early when possible [OK]
Hint: Early stopping DFS avoids unnecessary traversal [OK]
Common Mistakes:
  • Believing greedy approach works for sums
  • Confusing BFS with DFS for path sums
2. What is the time complexity of the optimal countNodes algorithm that uses binary search on the last level of a complete binary tree with n nodes?
medium
A. O(log n)
B. O(n)
C. O((log n)^2)
D. O(n log n)

Solution

  1. Step 1: Analyze height and binary search

    Height h = O(log n). Binary search on last level does O(log n) steps.
  2. Step 2: Combine existence checks

    Each existence check traverses height h = O(log n). Total time = O(log n) * O(log n) = O((log n)^2).
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Nested log factors from height and binary search [OK]
Hint: Two nested log factors multiply to (log n)^2 [OK]
Common Mistakes:
  • Confusing O(log n) with O((log n)^2)
  • Assuming linear time due to traversal
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. The following BFS-based code attempts to compute the maximum depth of a binary tree. Identify the line containing the subtle bug that causes incorrect depth calculation for an empty tree input.
from collections import deque

def maxDepth(root):
    queue = deque([root])
    depth = 0
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth
medium
A. Line 7: Using len(queue) to determine level size
B. Line 15: Incrementing depth after processing each level
C. Line 10: Popping node from queue without null check
D. Line 2: Initializing queue with root without checking if root is null

Solution

  1. Step 1: Check handling of empty tree

    Code initializes queue with root without checking if root is null, so if root is null, queue contains null, causing errors.
  2. Step 2: Verify other lines

    len(queue) and popping nodes are correct if queue is valid; depth increment is necessary after each level.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Missing root null check causes failure on empty tree [OK]
Hint: Always check for null root before queue initialization [OK]
Common Mistakes:
  • Not handling empty tree input
  • Assuming root always exists
  • Incrementing depth incorrectly
5. Suppose the problem is modified so that node values can be negative, and you want to find all root-to-leaf paths summing to targetSum. Which modification to the DFS approach is necessary to ensure correctness?
hard
A. Remove pruning and explore all paths fully since negative values can reduce sums
B. Add pruning to stop exploring paths when current_sum exceeds targetSum
C. Use BFS instead of DFS to avoid infinite loops caused by negative values
D. Sort children nodes by value to explore promising paths first

Solution

  1. Step 1: Understand effect of negative values

    Negative values can decrease current_sum, so pruning based on exceeding targetSum can miss valid paths.
  2. Step 2: Adjust DFS to remove pruning

    To ensure all valid paths are found, pruning must be removed and all paths fully explored.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Pruning breaks correctness with negative values; full exploration needed [OK]
Hint: Negative values invalidate pruning based on sum limits [OK]
Common Mistakes:
  • Applying pruning blindly
  • Switching to BFS unnecessarily
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard