Solving Symmetric Tree in JavaScript: Step-by-Step Guide

Introduction to the Symmetric Tree Problem

The Symmetric Tree problem is a classic binary tree challenge that frequently appears in coding interviews and algorithm practice platforms like LeetCode. At its core, the problem asks you to determine whether a binary tree is a mirror reflection of itself when divided down the middle. This means that the left subtree should be a mirror image of the right subtree at every level of the tree.

While the concept sounds straightforward, implementing an efficient solution requires a solid understanding of tree traversal techniques, recursion, and the ability to compare two subtrees simultaneously. In this tutorial, we will walk through the problem step by step, explore both recursive and iterative approaches in JavaScript, and discuss best practices to keep in mind.

Understanding the Problem

Before diving into code, let us clearly define what makes a tree symmetric. A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree. For two trees to be mirror images of each other, three conditions must hold true:

Their root nodes must contain the same value.
The left subtree of the first tree must be a mirror reflection of the right subtree of the second tree.
The right subtree of the first tree must be a mirror reflection of the left subtree of the second tree.

Consider the following example of a symmetric tree:

This tree is symmetric because every node on the left side has a corresponding mirror node on the right side with the same value. Now consider an asymmetric tree:

This tree is not symmetric because the left child of the left node 2 is missing while the left child of the right node 2 is also missing, but the right children are placed differently relative to the center.

Defining the Tree Node Structure

In JavaScript, we typically represent a binary tree node using a simple class. Here is the standard definition we will use throughout this tutorial:

class TreeNode {
  constructor(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
  }
}

This structure gives each node a value and pointers to its left and right children. With this in place, we can begin building our solutions.

Why the Symmetric Tree Problem Matters

The Symmetric Tree problem is more than just an interview exercise. It tests several fundamental computer science concepts simultaneously. First, it evaluates your understanding of tree data structures and recursive thinking. Trees are foundational structures used in file systems, databases, parsing expressions, and many other real-world applications.

Second, the problem requires you to compare two structures in parallel, which is a pattern that appears in many other algorithms. Whether you are comparing two JSON objects, validating palindromic structures, or checking if two graphs are isomorphic, the underlying technique of comparing mirrored structures remains relevant.

Finally, this problem offers an excellent opportunity to practice converting recursive solutions into iterative ones. Many candidates can solve it recursively but struggle with the iterative approach. Mastering both demonstrates a deeper understanding of how recursion maps to explicit stack or queue usage.

Approach 1: Recursive Solution

The recursive approach is the most intuitive way to solve this problem. The idea is to write a helper function that takes two nodes and checks whether they are mirrors of each other. We then call this helper function with the left and right children of the root.

Step-by-Step Logic

Here is how the recursive logic unfolds:

If both nodes are null, they are mirrors, so return true.
If only one of the nodes is null, they cannot be mirrors, so return false.
If both nodes exist but have different values, return false.
Recursively check if the left child of the first node mirrors the right child of the second node, and if the right child of the first node mirrors the left child of the second node.

Implementing the Recursive Solution

function isSymmetric(root) {
  if (root === null) {
    return true;
  }

  function isMirror(node1, node2) {
    // Both nodes are null - they are mirrors
    if (node1 === null && node2 === null) {
      return true;
    }

    // Only one node is null - not mirrors
    if (node1 === null || node2 === null) {
      return false;
    }

    // Values must match, and subtrees must be mirrors
    return (
      node1.val === node2.val &&
      isMirror(node1.left, node2.right) &&
      isMirror(node1.right, node2.left)
    );
  }

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

Testing the Recursive Solution

Let us test this function with a few examples to verify correctness:

// Example 1: Symmetric tree
//        1
//       / \
//      2   2
//     / \ / \
//    3  4 4  3
const tree1 = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(3),
    new TreeNode(4)
  ),
  new TreeNode(2,
    new TreeNode(4),
    new TreeNode(3)
  )
);
console.log(isSymmetric(tree1)); // Output: true

// Example 2: Asymmetric tree
//        1
//       / \
//      2   2
//       \   \
//        3   3
const tree2 = new TreeNode(1,
  new TreeNode(2,
    null,
    new TreeNode(3)
  ),
  new TreeNode(2,
    null,
    new TreeNode(3)
  )
);
console.log(isSymmetric(tree2)); // Output: false

// Example 3: Single node
const tree3 = new TreeNode(1);
console.log(isSymmetric(tree3)); // Output: true

// Example 4: Empty tree
console.log(isSymmetric(null)); // Output: true

Time and Space Complexity

The time complexity of the recursive solution is O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once during the comparison.

The space complexity is O(h), where h is the height of the tree. This accounts for the recursion stack. In the worst case of a skewed tree, the height could be n, making the space complexity O(n). For a balanced tree, the height is log(n), so the space complexity would be O(log n).

Approach 2: Iterative Solution Using a Queue

While the recursive solution is elegant, some interviewers may ask for an iterative approach. Additionally, deeply nested trees can cause stack overflow errors in JavaScript with recursion. The iterative approach uses a queue to process pairs of nodes level by level.

Step-by-Step Logic

The iterative approach works as follows:

Initialize a queue and enqueue the left and right children of the root.
While the queue is not empty, dequeue two nodes at a time.
If both nodes are null, continue to the next iteration.
If only one node is null or their values differ, return false.
Enqueue the children in mirror order: left child of the first node with right child of the second, and right child of the first node with left child of the second.
If the queue empties without finding a mismatch, return true.

Implementing the Iterative Solution

function isSymmetricIterative(root) {
  if (root === null) {
    return true;
  }

  const queue = [];
  queue.push(root.left);
  queue.push(root.right);

  while (queue.length > 0) {
    const node1 = queue.shift();
    const node2 = queue.shift();

    // Both null - continue checking other pairs
    if (node1 === null && node2 === null) {
      continue;
    }

    // One is null, the other is not - not symmetric
    if (node1 === null || node2 === null) {
      return false;
    }

    // Values differ - not symmetric
    if (node1.val !== node2.val) {
      return false;
    }

    // Enqueue children in mirror order
    queue.push(node1.left);
    queue.push(node2.right);
    queue.push(node1.right);
    queue.push(node2.left);
  }

  return true;
}

Testing the Iterative Solution

// Reusing the same test trees from above
console.log(isSymmetricIterative(tree1)); // Output: true
console.log(isSymmetricIterative(tree2)); // Output: false
console.log(isSymmetricIterative(tree3)); // Output: true
console.log(isSymmetricIterative(null));  // Output: true

Time and Space Complexity

The time complexity remains O(n) since we still visit every node once. The space complexity is O(n) in the worst case because the queue can hold up to n/2 nodes at the widest level of the tree. This is comparable to the recursive approach for skewed trees but may use more memory for balanced trees since the queue stores nodes across an entire level rather than a single path.

Approach 3: Iterative Solution Using a Stack

As an alternative to the queue-based approach, you can use a stack. The logic is nearly identical, but using a stack changes the order in which nodes are processed. This approach can be useful if you want to perform a depth-first comparison rather than a breadth-first one.

function isSymmetricStack(root) {
  if (root === null) {
    return true;
  }

  const stack = [];
  stack.push(root.left);
  stack.push(root.right);

  while (stack.length > 0) {
    const node1 = stack.pop();
    const node2 = stack.pop();

    if (node1 === null && node2 === null) {
      continue;
    }

    if (node1 === null || node2 === null) {
      return false;
    }

    if (node1.val !== node2.val) {
      return false;
    }

    stack.push(node1.left);
    stack.push(node2.right);
    stack.push(node1.right);
    stack.push(node2.left);
  }

  return true;
}

The time and space complexities are the same as the queue-based approach. The choice between stack and queue is largely a matter of preference, though the queue approach more naturally mirrors the level-by-level comparison concept.

Edge Cases to Consider

When implementing a solution to the Symmetric Tree problem, it is important to handle several edge cases correctly:

Empty tree: A null root should return true, as an empty tree is trivially symmetric.
Single node: A tree with only a root node is symmetric by definition.
Tree with null children: Ensure your solution correctly handles cases where one child is null and the other is not.
Deeply nested trees: For very deep trees, the recursive solution may hit the call stack limit. The iterative approach avoids this issue.
Large values: JavaScript handles large numbers natively, but be aware of potential precision issues if your tree values are extremely large.

Best Practices

Choose the Right Approach for Your Context

If you are in an interview setting and the tree depth is not a concern, the recursive solution is typically the cleanest and most readable. It directly expresses the mathematical definition of symmetry. However, if the interviewer asks about stack overflow risks or explicitly requests an iterative solution, be prepared to switch to the queue or stack approach.

Always Handle Null Checks First

One of the most common bugs in tree problems is failing to check for null before accessing node properties. Always verify that a node is not null before accessing its val, left, or right properties. In the recursive solution, the order of null checks matters: check for both-null first, then one-null, then value comparison.

Write Clear Test Cases

Testing is critical for tree problems because the structure can be tricky to visualize. Create test cases that cover symmetric trees, asymmetric trees, single-node trees, empty trees, and trees with null children at various positions. Here is a comprehensive test suite:

function runTests() {
  // Test 1: Symmetric tree
  const symmetric = new TreeNode(1,
    new TreeNode(2, new TreeNode(3), new TreeNode(4)),
    new TreeNode(2, new TreeNode(4), new TreeNode(3))
  );
  console.assert(isSymmetric(symmetric) === true, "Test 1 failed");

  // Test 2: Asymmetric tree
  const asymmetric = new TreeNode(1,
    new TreeNode(2, null, new TreeNode(3)),
    new TreeNode(2, null, new TreeNode(3))
  );
  console.assert(isSymmetric(asymmetric) === false, "Test 2 failed");

  // Test 3: Single node
  console.assert(isSymmetric(new TreeNode(1)) === true, "Test 3 failed");

  // Test 4: Empty tree
  console.assert(isSymmetric(null) === true, "Test 4 failed");

  // Test 5: Two levels, symmetric
  const twoLevel = new TreeNode(1,
    new TreeNode(2),
    new TreeNode(2)
  );
  console.assert(isSymmetric(twoLevel) === true, "Test 5 failed");

  // Test 6: Two levels, asymmetric values
  const asymmetricValues = new TreeNode(1,
    new TreeNode(2),
    new TreeNode(3)
  );
  console.assert(isSymmetric(asymmetricValues) === false, "Test 6 failed");

  // Test 7: Deeply symmetric tree
  const deep = new TreeNode(5,
    new TreeNode(4,
      new TreeNode(3, new TreeNode(2), new TreeNode(1)),
      new TreeNode(2, new TreeNode(1), new TreeNode(2))
    ),
    new TreeNode(4,
      new TreeNode(2, new TreeNode(2), new TreeNode(1)),
      new TreeNode(3, new TreeNode(1), new TreeNode(2))
    )
  );
  console.assert(isSymmetric(deep) === true, "Test 7 failed");

  console.log("All tests passed!");
}

runTests();

Consider Using a Helper Function

In the recursive approach, using a helper function like isMirror keeps the main function signature clean. This is especially important if the problem expects a specific function signature, such as isSymmetric(root). The helper function encapsulates the comparison logic without exposing it as part of the public API.

Be Mindful of JavaScript's Shift Performance

In the queue-based iterative solution, we use Array.prototype.shift() to dequeue elements. In JavaScript, shift() has O(n) time complexity because it reindexes all remaining elements. For large trees, this can degrade performance. If performance is critical, consider using a proper queue implementation or two stacks to achieve O(1) dequeue operations:

function isSymmetricOptimized(root) {
  if (root === null) return true;

  // Using two arrays to simulate an efficient queue
  let currentLevel = [root.left, root.right];

  while (currentLevel.length > 0) {
    const nextLevel = [];

    for (let i = 0; i < currentLevel.length; i += 2) {
      const node1 = currentLevel[i];
      const node2 = currentLevel[i + 1];

      if (node1 === null && node2 === null) continue;
      if (node1 === null || node2 === null) return false;
      if (node1.val !== node2.val) return false;

      nextLevel.push(node1.left, node2.right, node1.right, node2.left);
    }

    currentLevel = nextLevel;
  }

  return true;
}

This optimized version processes nodes level by level without the overhead of repeated shift() calls, making it more efficient for large inputs.

Common Mistakes to Avoid

When solving the Symmetric Tree problem, developers often make a few recurring mistakes. Being aware of these can save you significant debugging time.

Mistake 1: Comparing left with left and right with right. The key insight of this problem is that you must compare the left child of one subtree with the right child of the other. Comparing left-to-left and right-to-right checks whether two trees are identical, not whether they are mirrors.

Mistake 2: Forgetting to check node values. Some implementations correctly check the structure but forget to verify that the values at mirrored positions are equal. Always include the value comparison in your base case logic.

Mistake 3: Not handling the null root case. While an empty tree is trivially symmetric, failing to check for a null root at the beginning can lead to runtime errors when you try to access root.left or root.right.

Mistake 4: Confusing symmetric with identical. A tree is symmetric if it is a mirror of itself. Two separate trees being identical is a different problem. Make sure you understand the distinction before writing code.

Conclusion

The Symmetric Tree problem is an excellent exercise for strengthening your understanding of binary trees, recursion, and iterative traversal techniques. By comparing mirrored subtrees either recursively or with an explicit queue or stack, you can determine symmetry in O(n) time with clean, readable code. The recursive approach offers elegance and directness, while the iterative approaches provide safety against stack overflow and demonstrate your ability to translate recursive logic into imperative code. Whichever approach you choose, remember to handle edge cases carefully, write comprehensive tests, and always compare left children with right children to capture the mirror relationship correctly. With these techniques in your toolkit, you will be well-prepared to tackle this problem and similar tree-based challenges in both interviews and real-world development.