Symmetric Tree (DFS Approach)

▶

Steps

setup

Start isSymmetric with root node

The algorithm begins by checking if the root is null. Since root exists, it proceeds to call isMirror on root's left and right children (nodes with value 2).

💡 This step sets up the initial recursive comparison between the left and right subtrees of the root.

Line:

return isMirror(root.left, root.right) if root else True

💡 The symmetry check starts by comparing the two main subtrees of the root.

compare

Check if either node is null

The helper function isMirror checks if either node (t1 or t2) is null. Both nodes exist, so it proceeds to compare their values.

💡 Checking for null nodes is the base case for recursion and helps detect asymmetry early.

Line:

if not t1 or not t2:
    return t1 == t2

💡 Both nodes must exist to be symmetric; if one is null and the other is not, the tree is asymmetric.

compare

Compare node values

The algorithm compares the values of the two nodes (both 2). Since they are equal, it proceeds to recursively check their children in mirrored positions.

💡 Node values must match for symmetry; this check prevents unnecessary recursion if values differ.

Line:

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

💡 Matching node values are necessary for symmetry at this level.

traverse

Recurse on t1.left and t2.right

The algorithm recursively calls isMirror on t1.left (node 3) and t2.right (node 7) to check if these subtrees are mirrors.

💡 Recursion moves inward comparing left subtree's left child with right subtree's right child to check mirror symmetry.

Line:

return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

💡 Symmetry requires mirrored children to be symmetric as well.

compare

Check if either node is null (t1=3, t2=3)

At nodes 3 and 3, the algorithm checks if either is null. Both exist, so it proceeds to compare their values.

💡 Base case check for null nodes is repeated at each recursive call to detect asymmetry early.

Line:

if not t1 or not t2:
    return t1 == t2

💡 Both nodes must be present to be symmetric.

compare

Compare node values (3 vs 3)

The values of nodes 3 and 3 are equal, so the algorithm continues to recursively check their children.

💡 Matching values confirm potential symmetry at this node pair.

Line:

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

💡 Node values must match for symmetry at every pair.

traverse

Recurse on t1.left and t2.right (both null)

The algorithm recursively calls isMirror on t1.left and t2.right, both null, which returns true immediately.

💡 Null nodes on both sides indicate symmetry at leaf level.

Line:

if not t1 or not t2:
    return t1 == t2

💡 Leaves with no children are symmetric by definition.

traverse

Recurse on t1.right and t2.left (both null)

The algorithm recursively calls isMirror on t1.right and t2.left, both null, returning true immediately.

💡 Both null children confirm symmetry at this leaf pair.

Line:

if not t1 or not t2:
    return t1 == t2

💡 Leaf nodes with no children are symmetric.

return

Return true for nodes 3 and 3

Both recursive calls for nodes 3 and 3 returned true, so isMirror returns true for this pair, confirming symmetry here.

💡 Returning true bubbles up the confirmation that these subtrees are symmetric.

Line:

return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

💡 Symmetry at this node pair is confirmed by both children being symmetric.

traverse

Recurse on t1.right and t2.left (nodes 4 and 6)

The algorithm now recursively checks the other mirrored pair: t1.right (node 5 with value 4) and t2.left (node 6 with value 4).

💡 Checking the other mirrored child pair is necessary to confirm full subtree symmetry.

Line:

return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

💡 Both mirrored pairs must be symmetric for the whole subtree to be symmetric.

compare

Check if either node is null (t1=4, t2=4)

The algorithm checks if either node is null. Both nodes exist, so it proceeds to compare their values.

💡 Null check is repeated at each recursive call to detect asymmetry early.

Line:

if not t1 or not t2:
    return t1 == t2

💡 Both nodes must be present to be symmetric.

compare

Compare node values (4 vs 4)

The values of nodes 4 and 4 are equal, so the algorithm continues to recursively check their children.

💡 Matching values confirm potential symmetry at this node pair.

Line:

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

💡 Node values must match for symmetry at every pair.

traverse

Recurse on t1.left and t2.right (both null)

The algorithm recursively calls isMirror on t1.left and t2.right, both null, returning true immediately.

💡 Null nodes on both sides indicate symmetry at leaf level.

Line:

if not t1 or not t2:
    return t1 == t2

💡 Leaves with no children are symmetric by definition.

traverse

Recurse on t1.right and t2.left (both null)

The algorithm recursively calls isMirror on t1.right and t2.left, both null, returning true immediately.

💡 Both null children confirm symmetry at this leaf pair.

Line:

if not t1 or not t2:
    return t1 == t2

💡 Leaf nodes with no children are symmetric.

return

Return true for nodes 4 and 4

Both recursive calls for nodes 4 and 4 returned true, so isMirror returns true for this pair, confirming symmetry here.

💡 Returning true bubbles up the confirmation that these subtrees are symmetric.

Line:

return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

💡 Symmetry at this node pair is confirmed by both children being symmetric.

return

Return true for root's left and right subtrees

Both recursive calls for the root's left and right children returned true, so the entire tree is symmetric and the algorithm returns true.

💡 The final return confirms the entire tree is symmetric after all checks.

Line:

return isMirror(root.left, root.right) if root else True

💡 The tree is symmetric if all mirrored pairs are symmetric.

from typing import Optional

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

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        # STEP 2
        if not t1 or not t2:
            return t1 == t2
        # STEP 3
        if t1.val != t2.val:
            return False
        # STEP 4, 10
        return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

    # STEP 1, 16
    return isMirror(root.left, root.right) if root else True

📊

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

Watching each recursive call and comparison helps you understand how the algorithm checks mirror symmetry by comparing corresponding nodes in left and right subtrees.

Current node: 2

1223443

DFS Stack

2 (entered)t1=2 t2=31 (entered)

Current node: 2

1223443

DFS Stack

2 (entered)t1=2 t2=31 (entered)

Current node: 2

1223443

DFS Stack

2 (entered)t1=2 t2=31 (entered)

Current node: 4

1223443

DFS Stack

4 (entered)t1=4 t2=72 (left_done)t1=2 t2=31 (entered)

Current node: 4

1223443

DFS Stack

4 (entered)t1=4 t2=72 (left_done)t1=2 t2=31 (entered)

Current node: 4

1223443

DFS Stack

4 (entered)t1=4 t2=72 (left_done)t1=2 t2=31 (entered)

1223443

DFS Stack

4 (left_done)t1=4 t2=72 (left_done)t1=2 t2=31 (entered)

Return: true

1223443

DFS Stack

4 (right_done)t1=4 t2=72 (left_done)t1=2 t2=31 (entered)

Return: true

Current node: 2

1223443

DFS Stack

2 (right_done)t1=2 t2=31 (entered)

Return: true

Current node: 5

1223443

DFS Stack

2 (entered)t1=5 t2=61 (entered)

Current node: 5

1223443

DFS Stack

2 (entered)t1=5 t2=61 (entered)

Current node: 5

1223443

DFS Stack

2 (entered)t1=5 t2=61 (entered)

1223443

DFS Stack

5 (entered)t1=null t2=null2 (entered)t1=5 t2=61 (entered)

Return: true

1223443

DFS Stack

5 (right_done)t1=null t2=null2 (entered)t1=5 t2=61 (entered)

Return: true

Current node: 1

1223443

DFS Stack

1 (entered)

Return: true

1223443

Return: true

Key Takeaways

✓ The algorithm checks symmetry by recursively comparing mirrored pairs of nodes from left and right subtrees.

This insight is hard to see from code alone because the recursion intertwines two subtrees simultaneously.

✓ Early exits occur when one node is null and the other is not, or when node values differ, preventing unnecessary recursion.

Visualizing these early exits clarifies how the algorithm efficiently detects asymmetry.

✓ The final answer is true only if all mirrored node pairs are symmetric, demonstrated by the recursive returns bubbling up true.

Seeing the recursive returns helps understand how local symmetry checks combine into a global result.

Practice

1. You are given a binary tree and a target sum. The task is to find all root-to-leaf paths where the sum of the node values equals the target sum. Which algorithmic approach guarantees finding all such paths efficiently?

easy

A. Greedy traversal choosing the child with the closest value to the remaining sum

B. Depth-first search (DFS) with path tracking and backtracking to explore all root-to-leaf paths

C. Dynamic programming to store sums at each node and combine results bottom-up

D. Breadth-first search (BFS) with queue to find the shortest path matching the sum

Solution

1. Step 1: Understand problem requires all root-to-leaf paths

   Since we must find all paths, not just one, exhaustive exploration is needed.

2. Step 2: Identify DFS with path tracking and backtracking

   DFS explores each path fully, tracking the current path and sum, backtracking to explore alternatives.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DFS explores all paths, greedy or BFS do not guarantee all paths [OK]

Hint: All root-to-leaf paths require exhaustive DFS [OK]

Common Mistakes:

• Thinking greedy or BFS finds all paths
• Confusing DP for path enumeration

2. Consider the following iterative DFS code for finding all root-to-leaf paths with a given sum. Given the tree below and targetSum = 7, what is the final returned list? Tree structure: 5 / \ 4 8 / / \ 11 13 4 Target sum: 7

def pathSum(root, targetSum):
    if not root:
        return []
    res = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, current_sum = stack.pop()
        if not node.left and not node.right:
            if current_sum == targetSum:
                res.append(path)
        if node.right:
            stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
        if node.left:
            stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
    return res

easy

A. []

B. [[5, 4, 11]]

C. [[5, 4]]

D. [[5, 8, 4]]

Solution

1. Step 1: Trace paths and sums

   Paths: 5->4->11 sum=20, 5->8->13 sum=26, 5->8->4 sum=17; none equals 7.

2. Step 2: Confirm no leaf path sums to 7

   Since no leaf path sums to 7, result list remains empty.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No leaf path sums to 7, so empty list returned [OK]

Hint: Check sums only at leaf nodes [OK]

Common Mistakes:

• Confusing intermediate node sums with leaf sums
• Forgetting to check leaf condition

3. Consider the following iterative DFS code snippet for counting paths with sum equal to targetSum in a binary tree. Given the tree with root value 1, left child 2, right child 3, and targetSum = 3, what is the final value of result after the loop finishes?

class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0
        prefix_counts = {0: 1}
        result = 0
        stack = [(root, 0, False)]  # node, current_sum, visited_children

        while stack:
            node, current_sum, visited = stack.pop()
            if node is None:
                continue
            if not visited:
                current_sum += node.val
                result += prefix_counts.get(current_sum - targetSum, 0)
                prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
                stack.append((node, current_sum, True))  # Mark node as visited
                stack.append((node.right, current_sum, False))
                stack.append((node.left, current_sum, False))
            else:
                prefix_counts[current_sum] -= 1

        return result

easy

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Trace initial stack and prefix_counts

   Start with stack=[(1,0,False)], prefix_counts={0:1}, result=0.

2. Step 2: Process nodes and update result

   Paths summing to 3 are: (1->2) and (3) alone, total 2 paths counted.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two valid paths found matching target sum [OK]

Hint: Count paths by prefix sums during DFS traversal [OK]

Common Mistakes:

• Missing the single node path (3)
• Double counting paths due to prefix_counts not decremented
• Off-by-one in updating result

4. Identify the bug in the following Morris preorder traversal code snippet that causes the tree structure to remain modified after traversal:

def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                # Bug here
                current = current.right
    return result

medium

A. Line resetting predecessor.right to None is missing in the else block

B. Appending current.val before moving to left child is incorrect

C. The inner while loop condition should check predecessor.left instead of predecessor.right

D. The check for current.left being None should be after the else block

Solution

1. Step 1: Identify missing restoration of tree structure

   In Morris traversal, after visiting left subtree, predecessor.right must be reset to None to restore original tree.

2. Step 2: Locate missing line

   The else block lacks the line predecessor.right = None, causing the threaded link to persist.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without resetting, tree remains modified after traversal [OK]

Hint: Always reset threaded links to None after use [OK]

Common Mistakes:

• Forgetting to restore tree structure
• Appending nodes in wrong order
• Incorrect loop conditions

5. What is the time complexity of the iterative DFS solution for finding all root-to-leaf paths with a given sum in a binary tree with N nodes and maximum path length L?

medium

A. O(N) because each node is visited once

B. O(N^2) because all pairs of nodes are compared during traversal

C. O(N * L) because each node's path is copied when pushed onto the stack

D. O(L) because only the path length affects complexity

Solution

1. Step 1: Identify operations per node

   Each node is visited once, but path copying of length up to L occurs when pushing onto stack.

2. Step 2: Calculate total complexity

   Copying paths of length L for up to N nodes leads to O(N * L) time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Path copying dominates, so complexity is O(N * L) [OK]

Hint: Path copying causes O(N * L), not just O(N) [OK]

Common Mistakes:

• Assuming O(N) ignoring path copying
• Confusing with quadratic complexity from unrelated operations