Same Tree and Symmetric Tree Problems in Java

The same tree and symmetric tree problems are fundamental binary tree algorithms that test understanding of tree traversal and structural comparison techniques in FAANG interviews.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Are we checking if two trees are identical (Same Tree) or if one tree is symmetric around its center (Symmetric Tree)?
2. What's the expected input size range? Can we assume trees are balanced or could they be highly unbalanced?
3. Should we modify the input trees during our solution, or must we work with immutable structures?
4. How should we handle null nodes? Are they considered valid nodes or just missing children?
5. What's the target time complexity for follow-up? O(n) is expected, but are there specific constraints?

Restatement of the problem:

Given two binary trees, determine whether they are structurally identical and have the same node values. This is commonly known as "Same Tree" problem, though it can also refer to checking if a single tree is symmetric (mirror of itself).

Problem details:

• Input: Two binary tree roots (p and q)
• Output: Boolean indicating if trees are identical
• Constraints:
  • Tree nodes can have values in range [-100, 100]
  • Number of nodes in each tree can be up to 100
  • Trees may be empty (null root)
  • Node values can repeat

Assumptions:

• Both inputs are valid binary tree nodes
• We're comparing structural identity, not just value equality
• Null nodes are treated as equivalent (both missing)

Data shape and hidden structure: The problem involves comparing two binary tree structures recursively. Each node has left and right child pointers, and we must ensure both trees have matching structure and values at every corresponding position. The recursive nature suggests a divide-and-conquer approach where we compare nodes and their subtrees simultaneously.

The key insight is that this problem can be solved with a simple recursive traversal, comparing corresponding nodes in both trees at each step.

2. Pattern Recognition

The problem involves comparing two binary trees to determine if they are identical in structure and node values. This is a classic tree traversal problem that exhibits several key patterns:

Most likely pattern: Tree Traversal with Structural Comparison

The wording "same tree" and "symmetric tree" signals that we're dealing with structural equality checking. The key indicators are:

• "identical structure" - suggests we need to traverse both trees simultaneously
• "same values" - requires value comparison at each node
• "tree" - naturally fits tree traversal algorithms

Why this problem fits the pattern: This is fundamentally about validating that two binary trees are structurally and semantically identical. The problem maps directly to a recursive tree traversal where we compare corresponding nodes in both trees.

Core insight: The solution requires simultaneous traversal of both trees with the same traversal order (pre-order, in-order, or post-order). At each step, we must validate that:

1. Both nodes exist (or both are null)
2. If both exist, their values match
3. Their left subtrees are identical
4. Their right subtrees are identical

This pattern is fundamental to tree comparison problems and can be solved efficiently with either recursive or iterative approaches, but the recursive solution is most intuitive for this structure.

The hidden structure here is that we're essentially performing a simultaneous DFS on both trees, maintaining the correspondence between nodes in each tree throughout the traversal.

3. Approach Evolution

My first instinct is to solve this with a recursive approach because the problem has a natural recursive structure - we need to compare corresponding nodes in both trees, and this naturally forms a tree traversal pattern. But that's O(n²) in worst case if we're comparing every node to every other node, which is inefficient.

Let me think about how to optimize this. I notice that if I traverse both trees simultaneously in the same order, I can compare corresponding nodes directly. This is a classic "tree traversal" pattern where we're essentially doing a simultaneous DFS on both trees.

The key insight is that I don't need to store all nodes and then compare - I can traverse both trees in lockstep, comparing nodes as I go. This reduces the problem to a simple recursive comparison where at each step I check if current nodes match, then recursively check their left and right subtrees.

I'm going to use a recursive approach that compares nodes in the same position in both trees, which is O(n) time and O(h) space where h is the height of the tree. The invariant I need to maintain is that at any recursive call, I'm comparing corresponding nodes in both trees.

The approach works by:

1. If both nodes are null, they're equal (base case)
2. If only one is null, they're not equal (mismatch)
3. If both exist, check if values match and recursively check left and right subtrees
4. This naturally handles all edge cases including empty trees

This is optimal because we must examine each node at least once to determine if trees are identical, so O(n) is the best possible time complexity.

// Recursive approach - compare corresponding nodes in both trees
public boolean isSameTree(TreeNode p, TreeNode q) {
    // Base case: if both nodes are null, trees are same at this point
    if (p == null && q == null) return true;
    
    // If only one is null, trees differ
    if (p == null || q == null) return false;
    
    // If values don't match, trees are different
    if (p.val != q.val) return false;
    
    // Recursively check left and right subtrees
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

4. Data Structure Choice

For this tree problem, I'll use the standard TreeNode structure that's typical in binary tree problems.

Primary Data Structures:

• TreeNode class with val, left, and right fields - This is the fundamental building block for representing the binary tree structure
• Queue<TreeNode> or Stack<TreeNode> - For iterative traversal approaches (though I'll primarily use recursion for clarity)

Why Each Choice Is Needed:

• The TreeNode class is essential because it represents the core data structure we're operating on - each node contains the value and references to its children
• For iterative solutions, a Queue would be appropriate for level-order traversal or a Stack for depth-first traversal, but since we're comparing trees recursively, we don't need additional containers beyond the recursive call stack

Time and Space Impact:

• TreeNode objects are O(1) space per node in terms of storage overhead (just the three fields)
• The recursive approach uses O(h) space where h is the height of the tree for the call stack (O(log n) average case for balanced trees, O(n) worst case for skewed trees)
• No additional data structures are needed beyond what's required to represent the tree itself

Helper Structure:

• No helper structures are needed for the core logic, but we could use a Pair<TreeNode, TreeNode> if implementing an iterative solution that compares nodes simultaneously - though this is unnecessary for the recursive approach

The choice of TreeNode as our primary structure is natural and standard for binary tree problems, requiring no additional data structures to solve this specific problem efficiently.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Consider two symmetric trees:

Tree 1:     Tree 2:
    1           1
   / \         / \
  2   3       3   2
 / \         / \
4   5       5   4

Step 1: Call isSymmetric(root) where root has value 1.

• This calls isSameTree(root.left, root.right) with left subtree = [2,4,5] and right subtree = [3,5,4]

Step 2: Compare left subtree (2,4,5) with right subtree (3,5,4)

• Compare node values: 2 vs 3 → Not equal, so return false

Let me trace a truly symmetric case:

Tree 1:     Tree 2:
    1           1
   / \         / \
  2   2       2   2
 / \         / \
3   4       4   3

Step 1: Call isSymmetric(root) where root has value 1.

• This calls isSameTree(root.left, root.right) with left subtree = [2,3,4] and right subtree = [2,4,3]

Step 2: Compare left subtree (2,3,4) with right subtree (2,4,3)

• Compare node values: 2 vs 2 → Equal, continue
• Compare left subtrees (3) with right subtrees (4)
• Both are leaf nodes, so compare 3 vs 4 → Not equal, return false

Actually, let me trace a correct symmetric example:

Tree 1:     Tree 2:
    1           1
   / \         / \
  2   2       2   2
 / \         / \
3   3       3   3

Step 1: Call isSymmetric(root) where root has value 1.

• This calls isSameTree(root.left, root.right) with left subtree = [2,3,3] and right subtree = [2,3,3]

Step 2: Compare left subtree (2,3,3) with right subtree (2,3,3)

• Compare node values: 2 vs 2 → Equal, continue
• Compare left subtrees (3) with right subtrees (3)
• Both are leaf nodes, so compare 3 vs 3 → Equal, return true

The algorithm correctly identifies that the trees are symmetric by recursively checking that corresponding nodes have equal values and their subtrees form mirror images.

Edge case handling:

• When both nodes are null, we return true (base case)
• When only one node is null, we return false (asymmetric)
• When values differ, we return false immediately

The algorithm terminates correctly because every node is visited exactly once in the recursive calls, and all symmetric properties are checked through the recursive structure.

6. Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // Base case: both nodes are null
        if (p == null && q == null) {
            return true;
        }
        
        // One is null, the other is not - trees are different
        if (p == null || q == null) {
            return false;
        }
        
        // Both nodes exist - check if values match and recursively check subtrees
        return (p.val == q.val) && 
               isSameTree(p.left, q.left) && 
               isSameTree(p.right, q.right);
    }
    
    public boolean isSymmetric(TreeNode root) {
        // Symmetric tree is same as comparing left and right subtrees
        return isSameTree(root.left, root.right);
    }
}

The solution handles both problems in a clean, recursive manner:

• isSameTree compares two trees for structural and value equality
• isSymmetric leverages the same logic by comparing left and right subtrees of the root
• The recursive approach naturally handles all edge cases including null nodes
• Time complexity is O(min(m,n)) where m and n are the number of nodes in each tree
• Space complexity is O(max(h1,h2)) where h1,h2 are the heights due to recursion stack

7. Complexity Analysis

Time Complexity: O(min(m,n)) Where m and n are the number of nodes in the two trees being compared. In the worst case, we must visit every node in both trees to determine they are identical. Since we stop as soon as we find a mismatch, the actual time is bounded by the smaller of the two tree sizes.

Space Complexity: O(min(h₁,h₂)) Where h₁ and h₂ are the heights of the two trees. This space is used by the recursive call stack during tree traversal. In the worst case (completely unbalanced trees), space complexity becomes O(min(m,n)) due to deep recursion. For balanced trees, it's O(log min(m,n)).

Why these bounds are correct:

• The time bound is tight because we must examine each node at most once in the traversal, and the number of nodes processed is limited by the smaller tree size.
• The space bound is tight because the maximum recursion depth equals the height of the shallower tree, and we only store one recursive call frame at a time.

Optimality: This solution is optimal for the problem as stated. We must examine at least every node in both trees to verify identity, making O(min(m,n)) time complexity unavoidable. The space complexity is also optimal for recursive approaches since we must store the call stack depth.

The solution achieves the best possible trade-off between time and space complexity for this tree comparison problem, with no redundant operations or unnecessary data structures.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Both trees empty: Should return true - this is a base case that must be handled correctly
• One tree empty, other not: Should return false - common mistake is to only check if both nodes are null but forget the asymmetric case
• Single node trees: Must verify that both root nodes have identical values

Duplicate Values and Repeated States

• Trees with duplicate values can be valid symmetric trees (e.g., [1,2,2,3,4,4,3])
• The algorithm must compare actual structure and not just values - a symmetric tree requires mirror reflection of structure, not just matching values

Boundary Conditions

• Single node trees: A single node is symmetric with itself (both left and right children are null)
• Null nodes: Must handle null node comparisons properly to avoid NullPointerExceptions
• Deeply nested structures: Ensure recursive depth handling doesn't cause stack overflow for very deep trees

Common Implementation Mistakes

• Incorrect base case logic: Checking p.val == q.val before checking if both are null can cause NPE
• Missing null checks: Forgetting to check that one node is null while the other isn't
• Wrong recursive calls: Using isSameTree(p.left, q.right) and isSameTree(p.right, q.left) instead of proper symmetric matching
• Early termination: Returning too early without fully validating the mirror structure

Key Defensive Programming Points

// Common mistake - this can throw NPE:
if (p.val == q.val) { ... }

// Correct approach - check nulls first:
if (p == null && q == null) return true;
if (p == null || q == null) return false;
if (p.val != q.val) return false;

The most critical edge case is ensuring that null handling is consistent throughout the recursive calls, particularly when one subtree is deeper than the other.

9. Alternative Approaches

There are several alternative approaches to solving the symmetric tree problem, each with different trade-offs:

1. Iterative BFS/Level-order Traversal Instead of recursion, we can use a queue-based BFS approach to compare nodes level by level. We'd enqueue pairs of nodes to compare, ensuring we process symmetric positions together. This approach avoids potential stack overflow issues with very deep trees but requires additional space for the queue.

2. Tree Serialization + String Comparison Serialize both trees using a consistent traversal method (like pre-order with null markers) and compare the resulting strings. This is simple to implement but has higher space complexity due to string storage, and the serialization format must be carefully chosen to maintain structural information.

3. In-order and Post-order Traversal Combination We could use a combination of in-order and post-order traversals to create unique signatures for each tree structure. However, this approach is more complex and less intuitive than direct comparison.

4. Single Pass with Early Termination An iterative approach using a stack that processes nodes in pairs, similar to the recursive solution but avoiding function call overhead. This trades cleaner code for potentially better stack space efficiency.

The chosen recursive approach is preferred because it's the most readable, maintains clear logic flow, and has optimal time complexity. The iterative alternatives add unnecessary complexity for this specific problem while not providing significant advantages in most practical scenarios.

The recursive solution's elegance and clarity make it the preferred approach for interviews, even though iterative versions are technically viable.

10. Test Cases

// Test case 1: Identical trees
TreeNode tree1 = new TreeNode(1);
tree1.left = new TreeNode(2);
tree1.right = new TreeNode(3);

TreeNode tree2 = new TreeNode(1);
tree2.left = new TreeNode(2);
tree2.right = new TreeNode(3);

// Test case 2: Different structure
TreeNode tree3 = new TreeNode(1);
tree3.left = new TreeNode(2);

TreeNode tree4 = new TreeNode(1);
tree4.right = new TreeNode(3);

// Test case 3: Empty trees
TreeNode empty1 = null;
TreeNode empty2 = null;

// Test case 4: One empty tree
TreeNode tree5 = new TreeNode(1);
TreeNode empty3 = null;

// Test case 5: Symmetric tree
TreeNode sym1 = new TreeNode(1);
sym1.left = new TreeNode(2);
sym1.right = new TreeNode(2);
sym1.left.left = new TreeNode(3);
sym1.left.right = new TreeNode(4);
sym1.right.left = new TreeNode(4);
sym1.right.right = new TreeNode(3);

TreeNode sym2 = new TreeNode(1);
sym2.left = new TreeNode(2);
sym2.right = new TreeNode(2);
sym2.left.left = new TreeNode(3);
sym2.left.right = new TreeNode(4);
sym2.right.left = new TreeNode(4);
sym2.right.right = new TreeNode(3);

The test cases cover:

• Identical trees (should return true)
• Trees with different structures (should return false)
• Empty trees (should return true)
• One empty tree and one non-empty tree (should return false)
• Symmetric trees with matching structure and values (should return true)

The tricky case involves symmetric trees where the left and right subtrees are mirror images of each other, requiring careful handling of null nodes and proper value comparison at each level.

11. Final Summary

The core insight is that tree symmetry can be determined by checking if one subtree is the mirror reflection of another, which is elegantly solved through recursive structural comparison. This solution works by simultaneously traversing both trees in opposite directions (left-to-right vs right-to-left) while maintaining strict value equality constraints, achieving optimal O(n) time complexity where n is the number of nodes in the smaller tree. The recursive approach is both intuitive and efficient, avoiding unnecessary data structure overhead while clearly expressing the symmetric relationship between tree structures.