Symmetric Tree (DFS Approach)

🎯

Symmetric Tree (DFS Approach)

easyTREEAmazonMicrosoftGoogle

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

💡 This problem tests your understanding of tree traversal and how to compare two subtrees simultaneously. Beginners often struggle because they try to compare nodes in a linear fashion rather than recursively checking mirrored nodes.

📋

Problem Statement

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.

💡

Example

Input"root = [1,2,2,3,4,4,3]"

Outputtrue

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

Input"root = [1,2,2,null,3,null,3]"

Outputfalse

The left subtree's right child and right subtree's right child are not mirrors.

• Empty tree (null root) → true
• Single node tree → true
• Tree with only left children → false
• Tree with only right children → false

⚠️

Common Mistakes

Comparing left subtree with left subtree instead of mirrored right subtree

Incorrectly returns true for asymmetric trees

✅ Always compare left child of one subtree with right child of the other

Not handling null nodes properly in recursion

Runtime errors or incorrect false positives/negatives

✅ Add base cases to return true if both nodes are null, false if only one is null

Forgetting to check node values before recursing

Returns true for trees with different node values but symmetric structure

✅ Check if current node values are equal before recursive calls

Using recursion without early exit

Unnecessary recursive calls leading to slower performance

✅ Return false immediately when asymmetry is detected

🧠

Brute Force (Pure Recursion)

💡 Starting with a simple recursive check helps understand the problem deeply by directly comparing mirrored nodes without any optimization.

Intuition

Check if the left subtree and right subtree are mirror images by recursively comparing their nodes in a mirrored fashion.

Algorithm

1. If the root is null, return true (empty tree is symmetric).
2. Define a helper function that takes two nodes and checks if they are mirrors.
3. In the helper, if both nodes are null, return true.
4. If one is null and the other is not, return false.
5. Check if the current nodes have the same value and recursively check the left child of one with the right child of the other and vice versa.
6. Return the result of the helper function called on root's left and right children.

💡 The challenge is to realize that symmetry means comparing opposite children recursively, not just the same side.

</>

Code

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:
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        return (t1.val == t2.val) and isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

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

# Example usage:
# root = TreeNode(1, TreeNode(2), TreeNode(2))
# print(isSymmetric(root))  # Output: True

Line Notes

def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:Defines the recursive helper to compare two nodes for mirror symmetry

if not t1 and not t2:Base case: both nodes are null means symmetric at this branch

if not t1 or not t2:If one node is null and the other isn't, symmetry breaks here

return (t1.val == t2.val) and isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)Check current node values and recurse on opposite children to verify mirror

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) { val = x; }
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val) && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(2);
    //     System.out.println(new Solution().isSymmetric(root)); // true
    // }
}

Line Notes

public boolean isSymmetric(TreeNode root) {Entry point to check symmetry starting from root

if (root == null) return true;Empty tree is symmetric by definition

return isMirror(root.left, root.right);Start recursive mirror check on left and right subtrees

return (t1.val == t2.val) && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);Check current nodes and recurse on mirrored children

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return isMirror(root->left, root->right);
    }

private:
    bool isMirror(TreeNode* t1, TreeNode* t2) {
        if (!t1 && !t2) return true;
        if (!t1 || !t2) return false;
        return (t1->val == t2->val) && isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(2);
//     Solution sol;
//     cout << sol.isSymmetric(root) << endl; // Output: 1 (true)
//     return 0;
// }

Line Notes

bool isSymmetric(TreeNode* root) {Public method to start symmetry check

if (!root) return true;Empty tree is symmetric

return isMirror(root->left, root->right);Begin recursive mirror comparison

return (t1->val == t2->val) && isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);Check node values and recurse on mirrored children

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var isSymmetric = function(root) {
    if (!root) return true;

    function isMirror(t1, t2) {
        if (!t1 && !t2) return true;
        if (!t1 || !t2) return false;
        return (t1.val === t2.val) && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }

    return isMirror(root.left, root.right);
};

// Example usage:
// const root = new TreeNode(1, new TreeNode(2), new TreeNode(2));
// console.log(isSymmetric(root)); // true

Line Notes

var isSymmetric = function(root) {Main function to check if tree is symmetric

if (!root) return true;Empty tree is symmetric by default

function isMirror(t1, t2) {Helper function to recursively check mirror symmetry

return (t1.val === t2.val) && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);Compare current nodes and recurse on opposite children

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once in the recursion. The recursion stack can go as deep as the tree height h.

💡 For a tree with 1000 nodes and height 10, this means roughly 1000 operations and stack depth of 10.

Interview Verdict: Accepted

This approach is efficient and accepted for the problem constraints, making it a solid baseline solution.

🧠

Iterative Approach Using Queue (BFS)

💡 This approach replaces recursion with an explicit queue to avoid stack overflow and better control the traversal order.

Intuition

Use a queue to iteratively compare nodes in pairs, ensuring the left subtree and right subtree nodes are mirror images.

Algorithm

1. If root is null, return true.
2. Initialize a queue and enqueue root's left and right children.
3. While the queue is not empty, dequeue two nodes at a time.
4. If both nodes are null, continue.
5. If one is null or their values differ, return false.
6. Enqueue the children in mirrored order: left child of first node and right child of second node, then right child of first node and left child of second node.
7. If all pairs match, return true.

💡 The key is to always enqueue nodes in pairs that should be mirrors, maintaining the symmetry check iteratively.

</>

Code

from collections import deque
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:
    if not root:
        return True
    queue = deque([root.left, root.right])
    while queue:
        t1 = queue.popleft()
        t2 = queue.popleft()
        if not t1 and not t2:
            continue
        if not t1 or not t2:
            return False
        if t1.val != t2.val:
            return False
        queue.append(t1.left)
        queue.append(t2.right)
        queue.append(t1.right)
        queue.append(t2.left)
    return True

# Example usage:
# root = TreeNode(1, TreeNode(2), TreeNode(2))
# print(isSymmetric(root))  # Output: True

Line Notes

queue = deque([root.left, root.right])Initialize queue with the two subtrees to compare

t1 = queue.popleft()Pop first node of the pair to compare

if not t1 and not t2:Both null means symmetric at this position, continue

queue.append(t1.left)Enqueue children in mirrored order to maintain symmetry check

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) { val = x; }
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root.left);
        queue.add(root.right);

        while (!queue.isEmpty()) {
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null) return false;
            if (t1.val != t2.val) return false;
            queue.add(t1.left);
            queue.add(t2.right);
            queue.add(t1.right);
            queue.add(t2.left);
        }
        return true;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(2);
    //     System.out.println(new Solution().isSymmetric(root)); // true
    // }
}

Line Notes

Queue<TreeNode> queue = new LinkedList<>();Use queue to hold pairs of nodes to compare

TreeNode t1 = queue.poll();Retrieve first node of the pair

if (t1 == null && t2 == null) continue;Both null means symmetric at this position

queue.add(t1.left);Add children in mirrored order to queue

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);

        while (!q.empty()) {
            TreeNode* t1 = q.front(); q.pop();
            TreeNode* t2 = q.front(); q.pop();
            if (!t1 && !t2) continue;
            if (!t1 || !t2) return false;
            if (t1->val != t2->val) return false;
            q.push(t1->left);
            q.push(t2->right);
            q.push(t1->right);
            q.push(t2->left);
        }
        return true;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(2);
//     Solution sol;
//     cout << sol.isSymmetric(root) << endl; // Output: 1 (true)
//     return 0;
// }

Line Notes

queue<TreeNode*> q;Queue to hold pairs of nodes for iterative comparison

TreeNode* t1 = q.front(); q.pop();Pop first node of the pair

if (!t1 && !t2) continue;Both null nodes mean symmetry at this position

q.push(t1->left);Push children in mirrored order to maintain symmetry check

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var isSymmetric = function(root) {
    if (!root) return true;
    const queue = [root.left, root.right];
    while (queue.length) {
        const t1 = queue.shift();
        const t2 = queue.shift();
        if (!t1 && !t2) continue;
        if (!t1 || !t2) return false;
        if (t1.val !== t2.val) return false;
        queue.push(t1.left);
        queue.push(t2.right);
        queue.push(t1.right);
        queue.push(t2.left);
    }
    return true;
};

// Example usage:
// const root = new TreeNode(1, new TreeNode(2), new TreeNode(2));
// console.log(isSymmetric(root)); // true

Line Notes

const queue = [root.left, root.right];Initialize queue with the two subtrees

const t1 = queue.shift();Dequeue first node of the pair

if (!t1 && !t2) continue;Both null nodes mean symmetry at this position

queue.push(t1.left);Enqueue children in mirrored order for next comparisons

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is enqueued and dequeued once. The queue can hold up to O(n) nodes in the worst case.

💡 For 1000 nodes, this means about 1000 enqueue and dequeue operations, with memory proportional to the tree width.

Interview Verdict: Accepted

This iterative approach is equally efficient and avoids recursion stack issues, useful in constrained environments.

🧠

Optimized Recursive with Early Exit

💡 This approach is a refinement of the brute force recursion that adds early exits and cleaner code structure for better readability and slight performance gains.

Intuition

Use the same recursive mirror check but return false immediately when asymmetry is detected to avoid unnecessary recursion.

Algorithm

1. If root is null, return true.
2. Define a helper function that returns false immediately if nodes differ or one is null.
3. Recursively check mirrored children only if current nodes match.
4. Return the helper result for root's left and right children.

💡 Early exit reduces the number of recursive calls, improving efficiency especially for large asymmetric trees.

</>

Code

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:
        if not t1 or not t2:
            return t1 == t2
        if t1.val != t2.val:
            return False
        return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

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

# Example usage:
# root = TreeNode(1, TreeNode(2), TreeNode(2))
# print(isSymmetric(root))  # Output: True

Line Notes

if not t1 or not t2:Return false immediately if one node is null and the other isn't

return t1 == t2If both are null, return true; otherwise false

if t1.val != t2.val:Early exit if node values differ

return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)Recurse only if current nodes match

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) { val = x; }
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null || t2 == null) return t1 == t2;
        if (t1.val != t2.val) return false;
        return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(2);
    //     System.out.println(new Solution().isSymmetric(root)); // true
    // }
}

Line Notes

if (t1 == null || t2 == null) return t1 == t2;Return false immediately if only one node is null

if (t1.val != t2.val) return false;Early exit on value mismatch

return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);Recurse only if current nodes match

return isMirror(root.left, root.right);Start recursion from root's children

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return isMirror(root->left, root->right);
    }

private:
    bool isMirror(TreeNode* t1, TreeNode* t2) {
        if (!t1 || !t2) return t1 == t2;
        if (t1->val != t2->val) return false;
        return isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(2);
//     Solution sol;
//     cout << sol.isSymmetric(root) << endl; // Output: 1 (true)
//     return 0;
// }

Line Notes

if (!t1 || !t2) return t1 == t2;Return false if only one node is null, true if both null

if (t1->val != t2->val) return false;Early exit on value mismatch

return isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);Recurse only if current nodes match

return isMirror(root->left, root->right);Start recursion from root's children

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var isSymmetric = function(root) {
    if (!root) return true;

    function isMirror(t1, t2) {
        if (!t1 || !t2) return t1 === t2;
        if (t1.val !== t2.val) return false;
        return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }

    return isMirror(root.left, root.right);
};

// Example usage:
// const root = new TreeNode(1, new TreeNode(2), new TreeNode(2));
// console.log(isSymmetric(root)); // true

Line Notes

if (!t1 || !t2) return t1 === t2;Return false if only one node is null, true if both null

if (t1.val !== t2.val) return false;Early exit on value mismatch

return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);Recurse only if current nodes match

return isMirror(root.left, root.right);Start recursion from root's children

⏱

Complexity

TimeO(n)

SpaceO(h)

Early exits reduce unnecessary recursion calls but worst-case remains O(n). Stack depth is tree height h.

💡 For large trees, early exit can save many calls, making the code faster in practice.

Interview Verdict: Accepted

This is a clean, efficient recursive solution preferred in interviews for clarity and performance.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimized recursive approach is best for most interviews due to clarity and efficiency; iterative is useful if recursion depth is a concern.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Pure Recursion)	O(n)	O(h)	Yes (deep recursion)	N/A	Good to mention and understand, rarely coded fully
2. Iterative BFS Using Queue	O(n)	O(n)	No	N/A	Mention if recursion depth is a concern; coding optional
3. Optimized Recursive with Early Exit	O(n)	O(h)	Yes (deep recursion)	N/A	Preferred approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and confirm input/output format.Step 2: Describe the brute force recursive approach to check mirrored nodes.Step 3: Discuss iterative BFS approach to avoid recursion stack issues.Step 4: Present optimized recursive approach with early exits.Step 5: Code your chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of tree traversal, recursion, and ability to handle edge cases and optimize code.

Common Follow-ups

• What if the tree is very deep? → Use iterative approach to avoid stack overflow.
• Can you do this with BFS? → Yes, use a queue to compare nodes iteratively.

💡 These follow-ups check your flexibility and understanding of recursion vs iteration tradeoffs.

🔍

Pattern Recognition

When to Use

1) Problem involves checking if a tree is symmetric or a mirror image. 2) Requires comparing two subtrees simultaneously. 3) Recursion or BFS can be used to traverse. 4) Node values and structure both matter.

Signature Phrases

mirror of itselfsymmetric around its centercheck if tree is symmetric

NOT This Pattern When

Checking if a tree is balanced or height-balanced is a different pattern focused on height, not symmetry.

Similar Problems

Invert Binary Tree - related by mirroring subtreesSame Tree - checks if two trees are identicalSubtree of Another Tree - checks subtree structure similarity

Practice

1. Consider the following code implementing the optimal House Robber III solution. Given the tree: 3 / \ 2 3 \ \ 3 1 What is the value of rob_current when dfs is called on the root node (value 3)?

easy

A. 7

B. 6

C. 8

D. 9

Solution

1. Step 1: Trace dfs on left child (value 2)

   dfs(2) calls dfs(null) and dfs(3). dfs(null) returns (0,0). dfs(3) returns (3,0) because it has no children. So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(0,0)=0. dfs(3) returns (3,0). For node 2: rob_current=2+0+0=2, not_rob_current=max(0,3)+max(0,0)=3. dfs(2) returns (2,3).

2. Step 2: Trace dfs on right child (value 3)

   dfs(3) calls dfs(null) and dfs(1). dfs(1) returns (1,0). So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(1,0)=1. dfs(3) returns (3,1).

3. Step 3: Calculate rob_current at root (value 3)

   rob_current = 3 + left[1] + right[1] = 3 + 3 + 1 = 7.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sum matches known example output 7 [OK]

Hint: Add node.val + not_rob of children for rob_current [OK]

Common Mistakes:

• Mixing rob and not_rob values for children
• Off-by-one in recursion returns

2. Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? Tree structure: - root = TreeNode(5) - root.left = TreeNode(4) - root.right = TreeNode(8) - root.left.left = TreeNode(11) - root.left.left.left = TreeNode(7) - root.left.left.right = TreeNode(2) - root.right.left = TreeNode(13) - root.right.right = TreeNode(4) - root.right.right.right = TreeNode(1)

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if not node.left and not node.right:
            return curr_sum == targetSum
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)

easy

A. True

B. False

C. Raises an exception due to null pointer

D. Returns True only if the root value equals targetSum

Solution

1. Step 1: Trace the path sums

   Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.

2. Step 2: Confirm code logic

   The DFS returns True as soon as it finds the matching path sum at a leaf node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Path 5↔4↔11↔2 sums to 22, so return True [OK]

Hint: Check all root-to-leaf paths, not just partial sums [OK]

Common Mistakes:

• Stopping at non-leaf nodes
• Ignoring leaf node condition

3. Examine the following buggy code snippet for computing the maximum path sum in a binary tree. Which line contains the subtle bug that causes incorrect results on trees with negative node values?

def maxPathSum(root):
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max_gain(node.left)
        right_gain = max_gain(node.right)
        current_path_sum = node.val + left_gain + right_gain
        max_sum = max(max_sum, current_path_sum)
        # Bug: returns sum of both left and right gains to parent
        return node.val + left_gain + right_gain

    max_gain(root)
    return max_sum

medium

A. Line returning 0 for null node

B. Line computing current_path_sum = node.val + left_gain + right_gain

C. Line updating max_sum = max(max_sum, current_path_sum)

D. Line returning node.val + left_gain + right_gain

Solution

1. Step 1: Understand return value meaning

   The function returns the maximum gain from the current node to its parent, which must be a single path (not both children).

2. Step 2: Identify the bug

   Returning node.val + left_gain + right_gain sums both children, which is invalid for parent gain; only one child path can be extended.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Return should be node.val + max(left_gain, right_gain) [OK]

Hint: Return value must be single path gain, not sum of both children [OK]

Common Mistakes:

• Returning sum of both children gains
• Ignoring negative gains
• Updating max_sum incorrectly

4. The following code attempts to compute the diameter of a binary tree using an optimized recursive approach. Identify the line containing the subtle bug that causes incorrect diameter calculation.

medium

A. Line 6: if not node: return 0

B. Line 9: diameter = max(diameter, left + right + 1)

C. Line 10: return 1 + max(left, right)

D. Line 2: diameter = 0

Solution

1. Step 1: Understand diameter definition counts edges, not nodes.

   The diameter is the number of edges on the longest path, so it should be left + right, not left + right + 1.

2. Step 2: Identify the bug line.

   Line 9 adds 1 incorrectly, causing diameter to be off by one.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Diameter must be sum of left and right heights (edges), not nodes [OK]

Hint: Diameter counts edges = left + right, not +1 [OK]

Common Mistakes:

• Adding 1 to diameter sum
• Not using nonlocal for diameter
• Returning wrong height value

5. Examine the following buggy code snippet for summing root-to-leaf numbers using DFS recursion. Which line contains the subtle bug causing incorrect sums on some inputs?

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.total = 0
        def dfs(node, current_number):
            if not node:
                return
            current_number = current_number * 10 + node.val
            self.total += current_number  # Bug here
            if not node.left and not node.right:
                return
            dfs(node.left, current_number)
            dfs(node.right, current_number)
        dfs(root, 0)
        return self.total

medium

A. Line with 'if not node:' return statement

B. Line adding current_number to self.total

C. Line checking if node is leaf

D. Line calling dfs on node.right

Solution

1. Step 1: Understand when sums should be added

   Sum should only include complete root-to-leaf numbers, so addition must happen only at leaf nodes.

2. Step 2: Identify incorrect addition

   Adding current_number at every node (including non-leaf) causes partial numbers to be summed, inflating total incorrectly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum only at leaves fixes the bug [OK]

Hint: Add to total only at leaf nodes [OK]

Common Mistakes:

• Adding partial path sums at non-leaf nodes
• Not resetting total between calls