Symmetric Tree

Easy · Trees · Explanation and code example

Breadth First Search

How it works

BFS processes nodes level by level using a queue. For symmetry checking, we enqueue pairs of nodes that should be mirrors. Processing the queue ensures we compare nodes at the same depth before moving deeper. This approach gives a level-by-level validation of the mirror property.

Steps

  1. Initialize a queue with the pair (root.left, root.right).
  2. While the queue is not empty:
    • For each pair in the current level:
      • Dequeue a pair.
      • If both are null, continue.
      • If only one is null or values differ, return false.
      • Enqueue pairs: (left.left, right.right) and (left.right, right.left).
  3. If all comparisons pass, return true.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Things to watch for

Comparing Wrong Node Pairs

A frequent mistake is comparing left.left with right.left instead of left.left with right.right. For a mirror reflection, the left child of the left subtree must match the right child of the right subtree, and vice versa.

Forgetting to Handle Null Cases First

When checking symmetry, you must handle the null cases before accessing node values. Checking left.val == right.val when either node is null will cause a null pointer exception. Always check if both are null (return true) or only one is null (return false) before comparing values.

Python code example

from typing import Optional
from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        queue = deque([(root.left, root.right)])
        while queue:
            for _ in range(len(queue)):
                left, right = queue.popleft()
                if not left and not right:
                    continue
                if not left or not right or left.val != right.val:
                    return False
                queue.append((left.left, right.right))
                queue.append((left.right, right.left))

        return True

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;

        queue<pair<TreeNode*, TreeNode*>> queue;
        queue.push({root->left, root->right});

        while (!queue.empty()) {
            for (int i = queue.size(); i > 0; i--) {
                auto [left, right] = queue.front();
                queue.pop();

                if (!left && !right) continue;
                if (!left || !right || left->val != right->val) {
                    return false;
                }
                queue.push({left->left, right->right});
                queue.push({left->right, right->left});
            }
        }

        return true;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations