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 need to output all nodes of a binary tree such that each node is processed only after its left and right children have been processed. Which traversal approach guarantees this order?

easy

A. Postorder traversal using depth-first search

B. Preorder traversal using recursion

C. Level-order traversal using a queue

D. Inorder traversal using recursion

Solution

1. Step 1: Understand traversal order requirements

   Postorder traversal processes left subtree, then right subtree, then the node itself, ensuring children are processed before the parent.

2. Step 2: Compare with other traversals

   Preorder and inorder do not guarantee children processed before parent; level-order processes nodes by depth, not child-first.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Postorder traversal matches the problem's processing order [OK]

Hint: Postorder processes children before parent [OK]

Common Mistakes:

• Confusing inorder with postorder
• Thinking preorder processes children first

2. You are given two arrays representing the inorder and postorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant searches?

easy

A. Use a greedy approach by always attaching nodes as left children when possible.

B. Use dynamic programming to store subtrees and avoid recomputation.

C. Use recursion with a hash map to quickly find root indices in the inorder array.

D. Use breadth-first search to reconstruct the tree level by level.

Solution

1. Step 1: Understand the problem constraints

   Reconstructing a tree from inorder and postorder requires identifying root nodes and splitting subtrees efficiently.

2. Step 2: Evaluate approaches

   Recursion with a hash map allows O(1) root index lookup in inorder, avoiding repeated linear searches and ensuring O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map lookup avoids O(n) search per recursion [OK]

Hint: Hash map lookup avoids repeated linear searches [OK]

Common Mistakes:

• Assuming greedy or BFS can reconstruct tree uniquely
• Confusing DP with tree construction
• Ignoring index lookup cost

3. 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

4. Suppose you want to perform inorder traversal on a binary tree where nodes can have parent pointers but no left or right child pointers. Which approach correctly produces the inorder sequence without recursion or extra stack?

hard

A. Use Morris traversal by creating threads on parent pointers instead of child pointers.

B. Use breadth-first search since parent pointers allow level order traversal.

C. Use recursive traversal ignoring parent pointers, which will fail due to missing child links.

D. Use iterative traversal with a pointer to the current node and track previously visited node to decide traversal direction.

Solution

1. Step 1: Understand traversal constraints

   Without left/right child pointers, Morris traversal is not applicable since it relies on child links.

2. Step 2: Use parent pointers to simulate traversal

   By tracking current and previously visited nodes, we can move up or down the tree to simulate inorder traversal iteratively.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Tracking previous node enables correct traversal without extra space [OK]

Hint: Parent pointers + prev node tracking enable traversal [OK]

Common Mistakes:

• Trying to create threads on parent pointers
• Using recursion without child pointers
• Confusing BFS with inorder traversal

5. If the binary tree nodes can have parent pointers in addition to left and right children, which modification to the iterative one-stack postorder traversal algorithm can eliminate the need for the last_visited variable?

hard

A. Use the parent pointer to move back up after visiting a node's children, tracking traversal direction

B. Push nodes twice onto the stack to simulate postorder without tracking last visited

C. Perform a preorder traversal and reverse the output list at the end

D. Use two stacks: one for traversal and one for output, ignoring parent pointers

Solution

1. Step 1: Understand role of last_visited

   Last_visited tracks if right child was processed to avoid revisiting; parent pointers can provide traversal direction.

2. Step 2: Use parent pointer to detect traversal direction

   By moving up via parent pointer, algorithm knows if coming from left or right child, eliminating need for last_visited.

3. Step 3: Compare other options

   Options B and D ignore parent pointers; A reverses preorder but does not leverage parent pointers; C uses parent pointers effectively.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Parent pointers enable direction-aware traversal without extra state [OK]

Hint: Parent pointers track traversal direction, removing last_visited [OK]

Common Mistakes:

• Ignoring parent pointers
• Using two stacks unnecessarily
• Reversing preorder output without parent info