Symmetric Tree in JavaScript (Time Complexity: O(n))

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

Understanding the Problem

The core challenge of this problem is to determine if a binary tree is symmetric around its center. This means that the left subtree should be a mirror reflection of the right subtree.

Common applications of this problem include validating data structures that need to be symmetric, such as certain types of balanced trees.

Potential pitfalls include not correctly handling null nodes or assuming that the tree is always balanced.

Approach

To solve this problem, we can use two main approaches: recursive and iterative.

Naive Solution

A naive solution might involve traversing the tree and comparing nodes, but without a clear strategy, this can become complex and inefficient.

Optimized Solutions

We can optimize our approach by using recursion or iteration to compare the left and right subtrees systematically.

Recursive Approach

In the recursive approach, we define a helper function that takes two nodes and checks if they are mirrors of each other. This function will be called on the left and right children of the root.

Iterative Approach

In the iterative approach, we use a queue to perform a level-order traversal, ensuring that corresponding nodes in the left and right subtrees are mirrors of each other.

Algorithm

Recursive Approach

Define a helper function isMirror that takes two nodes.
Check if both nodes are null; if so, return true.
If only one of the nodes is null, return false.
Check if the values of the two nodes are equal.
Recursively call isMirror on the left child of the first node and the right child of the second node, and vice versa.

Iterative Approach

Initialize a queue and enqueue the left and right children of the root.
While the queue is not empty, dequeue two nodes and compare them.
If both nodes are null, continue to the next iteration.
If only one of the nodes is null, return false.
Check if the values of the two nodes are equal.
Enqueue the left child of the first node and the right child of the second node, and vice versa.

Code Implementation

Recursive Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isSymmetric(root) {
    // Helper function to check if two trees are mirrors of each other
    function isMirror(t1, t2) {
        // If both nodes are null, they are mirrors
        if (t1 === null && t2 === null) return true;
        // If only one of the nodes is null, they are not mirrors
        if (t1 === null || t2 === null) return false;
        // Check if the current nodes' values are equal and their children are mirrors
        return (t1.val === t2.val) && 
               isMirror(t1.right, t2.left) && 
               isMirror(t1.left, t2.right);
    }
    // Start the recursion with the left and right children of the root
    return isMirror(root.left, root.right);
}

Iterative Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isSymmetric(root) {
    if (!root) return true;
    // Initialize a queue to hold nodes to be compared
    let queue = [];
    queue.push(root.left);
    queue.push(root.right);
    
    while (queue.length > 0) {
        // Dequeue two nodes to compare
        let t1 = queue.shift();
        let t2 = queue.shift();
        
        // If both nodes are null, continue to the next pair
        if (!t1 && !t2) continue;
        // If only one of the nodes is null, the tree is not symmetric
        if (!t1 || !t2) return false;
        // If the values of the nodes are not equal, the tree is not symmetric
        if (t1.val !== t2.val) return false;
        
        // Enqueue the children of the nodes in the correct order
        queue.push(t1.left);
        queue.push(t2.right);
        queue.push(t1.right);
        queue.push(t2.left);
    }
    
    return true;
}

Complexity Analysis

Both the recursive and iterative solutions have a time complexity of O(n), where n is the number of nodes in the tree. This is because each node is visited once.

The space complexity for the recursive solution is O(h), where h is the height of the tree, due to the recursion stack. For the iterative solution, the space complexity is O(n) due to the queue.

Edge Cases

Potential edge cases include:

An empty tree (should return true).
A tree with only one node (should return true).
Subtrees with different structures but the same node values (should return false).

Testing

To test the solution comprehensively, consider the following test cases:

An empty tree: root = []
A single-node tree: root = [1]
A symmetric tree: root = [1,2,2,3,4,4,3]
A non-symmetric tree: root = [1,2,2,null,3,null,3]

Use a testing framework like Jest or Mocha to automate these tests.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable parts.
Think about the properties of the data structure (e.g., symmetry in trees).
Consider both recursive and iterative solutions.
Write pseudocode to outline your approach before coding.

Conclusion

Understanding and solving the symmetric tree problem helps improve your skills in tree traversal and recursion. Practice with similar problems to strengthen your problem-solving abilities.

Additional Resources

For further reading and practice, consider the following resources: