Symmetric Tree

Problem Statement

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

A tree is symmetric if its structure mirrors across the center and all corresponding node values are equal.

What to notice first

• A symmetric tree has identical structure on both sides of the root.
• Each left subtree must mirror the right subtree: left’s left child pairs with right’s right child, and left’s right child pairs with right’s left child.
• Only the structure and values matter—the positions in memory do not.

Examples

Tree	Symmetric?	Explanation
[1, 2, 2, 3, 4, 4, 3]	✓ Yes	Mirror structure: 2 on left mirrors 2 on right, children are symmetric pairs
[1, 2, 2, null, 3, null, 3]	✗ No	Both children 3 are on the right side, not mirrored
[1]	✓ Yes	Single node is symmetric by definition

Constraints

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

Real-World Applications

Where this pattern appears

• GUI layout validation — check if a window’s component layout is balanced and symmetric.
• Configuration validation — verify that left and right configurations in a system match (e.g., disk mirror verification).
• Data structure validation — ensure tree-based index or search structures maintain balance.
• Molecular structure analysis — determine if molecular graphs have mirror symmetry.
• Image processing — detect symmetry in image pyramids or multi-scale representations.

Complexity Comparison

Approach	Time	Space	When Best
DFS Recursive	O(n)	O(h)	General case, simple logic, or shallow trees
BFS Iterative	O(n)	O(w)	Avoid stack overflow, wide trees, or level-wise analysis

* h = tree height; w = max width at any level

Which approach should you learn first?

• Pick DFS Recursive if you are comfortable with recursion and want the most concise solution.
• Pick BFS Iterative if you prefer iterative logic or expect very deep trees.

Most Common

DFS Recursive

O(n) time · O(h) space

Iterative Alternative

BFS Iterative

O(n) time · O(w) space

Approach 1: DFS Recursive (Recommended)

★ Recommended

Check if two subtrees are mirrors of each other. For each pair of nodes at corresponding positions, verify that their values are equal and their children form mirror pairs.

The key insight is to compare the left and right subtrees as mirror images: the left’s left child should match the right’s right child, and the left’s right child should match the right’s left child.

⏱ Time O(n) Visit each node once 💾 Space O(h) Call stack depth

Step-by-step Example

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

    1
   / \
  2   2     <- These are mirrors if their children match in mirror fashion
 / \ / \
3  4 4  3   <- Symmetric pairs verified

Step	Compare	Action
1	isMirror(root, root) start	Compare root’s left and right subtrees
2	Both nodes exist, values match (2 == 2)	Check children in mirror order
3	Left’s left (3) mirrors right’s right (3) ✓	Left’s right (4) mirrors right’s left (4) ✓
4	All leaf comparisons match	Return true

Animated walkthrough

How the mirror comparison finds symmetry

Use Next or Autoplay to watch the algorithm compare left and right subtrees, checking that they mirror each other at each level.

Back Autoplay Next Reset

Step 1 of 3 Target: symmetric

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function isSymmetric(root):
    return isMirror(root, root)

function isMirror(left, right):
    if left is null and right is null:
        return true
    if left is null or right is null:
        return false
    if left.val != right.val:
        return false
    return isMirror(left.left, right.right) and
           isMirror(left.right, right.left)

Solution Code

Python

symmetric_tree_dfs.py

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 is_symmetric_dfs(root: Optional[TreeNode]) -> bool:
    """
    Check if a binary tree is symmetric using DFS recursion.

    Time Complexity: O(n) - visit each node once
    Space Complexity: O(h) - recursion stack, where h is height
    """
    def is_mirror(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
        # Both nodes are None - symmetric
        if not left and not right:
            return True

        # One node is None or values differ - not symmetric
        if not left or not right:
            return False
        if left.val != right.val:
            return False

        # Recursively check: left's left with right's right
        # and left's right with right's left (mirror pattern)
        return is_mirror(left.left, right.right) and is_mirror(left.right, right.left)

    return is_mirror(root, root)


# Test cases
if __name__ == "__main__":
    # Example 1: Symmetric tree
    #       1
    #      / \
    #     2   2
    #    / \ / \
    #   3  4 4  3
    root1 = TreeNode(1)
    root1.left = TreeNode(2)
    root1.right = TreeNode(2)
    root1.left.left = TreeNode(3)
    root1.left.right = TreeNode(4)
    root1.right.left = TreeNode(4)
    root1.right.right = TreeNode(3)
    print(is_symmetric_dfs(root1))  # True

    # Example 2: Not symmetric
    #       1
    #      / \
    #     2   2
    #      \   \
    #       3   3
    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.right = TreeNode(2)
    root2.left.right = TreeNode(3)
    root2.right.right = TreeNode(3)
    print(is_symmetric_dfs(root2))  # False

C++

symmetric_tree_dfs.cpp

#include <iostream>
#include <memory>

using namespace std;

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

class Solution {
public:
    /**
     * Check if a binary tree is symmetric using DFS recursion.
     *
     * Time Complexity: O(n) - visit each node once
     * Space Complexity: O(h) - recursion stack, where h is height
     */
    bool isSymmetric(TreeNode* root) {
        return isMirror(root, root);
    }

private:
    bool isMirror(TreeNode* left, TreeNode* right) {
        // Both nodes are null - symmetric
        if (!left && !right) {
            return true;
        }

        // One node is null or values differ - not symmetric
        if (!left || !right) {
            return false;
        }
        if (left->val != right->val) {
            return false;
        }

        // Recursively check: left's left with right's right
        // and left's right with right's left (mirror pattern)
        return isMirror(left->left, right->right) &&
               isMirror(left->right, right->left);
    }
};

// Test cases
int main() {
    Solution sol;

    // Example 1: Symmetric tree
    //       1
    //      / \
    //     2   2
    //    / \ / \
    //   3  4 4  3
    TreeNode* root1 = new TreeNode(1);
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(2);
    root1->left->left = new TreeNode(3);
    root1->left->right = new TreeNode(4);
    root1->right->left = new TreeNode(4);
    root1->right->right = new TreeNode(3);
    cout << (sol.isSymmetric(root1) ? "true" : "false") << endl; // true

    // Example 2: Not symmetric
    //       1
    //      / \
    //     2   2
    //      \   \
    //       3   3
    TreeNode* root2 = new TreeNode(1);
    root2->left = new TreeNode(2);
    root2->right = new TreeNode(2);
    root2->left->right = new TreeNode(3);
    root2->right->right = new TreeNode(3);
    cout << (sol.isSymmetric(root2) ? "true" : "false") << endl; // false

    return 0;
}

Java

symmetric_tree_dfs.java

public class SymmetricTreeDFS {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * Check if a binary tree is symmetric using DFS recursion.
     *
     * Time Complexity: O(n) - visit each node once
     * Space Complexity: O(h) - recursion stack, where h is height
     */
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        // Both nodes are null - symmetric
        if (left == null && right == null) {
            return true;
        }

        // One node is null or values differ - not symmetric
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }

        // Recursively check: left's left with right's right
        // and left's right with right's left (mirror pattern)
        return isMirror(left.left, right.right) &&
               isMirror(left.right, right.left);
    }

    // Test cases
    public static void main(String[] args) {
        SymmetricTreeDFS sol = new SymmetricTreeDFS();

        // Example 1: Symmetric tree
        //       1
        //      / \
        //     2   2
        //    / \ / \
        //   3  4 4  3
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(2);
        root1.left.left = new TreeNode(3);
        root1.left.right = new TreeNode(4);
        root1.right.left = new TreeNode(4);
        root1.right.right = new TreeNode(3);
        System.out.println(sol.isSymmetric(root1)); // true

        // Example 2: Not symmetric
        //       1
        //      / \
        //     2   2
        //      \   \
        //       3   3
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(2);
        root2.left.right = new TreeNode(3);
        root2.right.right = new TreeNode(3);
        System.out.println(sol.isSymmetric(root2)); // false
    }
}

JavaScript

symmetric_tree_dfs.js

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

function isSymmetricDFS(root) {
    /**
     * Check if a binary tree is symmetric using DFS recursion.
     *
     * Time Complexity: O(n) - visit each node once
     * Space Complexity: O(h) - recursion stack, where h is height
     */
    function isMirror(left, right) {
        // Both nodes are null - symmetric
        if (!left && !right) {
            return true;
        }

        // One node is null or values differ - not symmetric
        if (!left || !right) {
            return false;
        }
        if (left.val !== right.val) {
            return false;
        }

        // Recursively check: left's left with right's right
        // and left's right with right's left (mirror pattern)
        return isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }

    return isMirror(root, root);
}

// Test cases
if (require.main === module) {
    // Example 1: Symmetric tree
    //       1
    //      / \
    //     2   2
    //    / \ / \
    //   3  4 4  3
    const root1 = new TreeNode(1);
    root1.left = new TreeNode(2);
    root1.right = new TreeNode(2);
    root1.left.left = new TreeNode(3);
    root1.left.right = new TreeNode(4);
    root1.right.left = new TreeNode(4);
    root1.right.right = new TreeNode(3);
    console.log(isSymmetricDFS(root1)); // true

    // Example 2: Not symmetric
    //       1
    //      / \
    //     2   2
    //      \   \
    //       3   3
    const root2 = new TreeNode(1);
    root2.left = new TreeNode(2);
    root2.right = new TreeNode(2);
    root2.left.right = new TreeNode(3);
    root2.right.right = new TreeNode(3);
    console.log(isSymmetricDFS(root2)); // false
}

module.exports = isSymmetricDFS;

Rust

symmetric_tree_dfs.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

pub struct Solution;

impl Solution {
    /// Check if a binary tree is symmetric using DFS recursion.
    ///
    /// Time Complexity: O(n) - visit each node once
    /// Space Complexity: O(h) - recursion stack, where h is height
    pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        fn is_mirror(
            left: &Option<Rc<RefCell<TreeNode>>>,
            right: &Option<Rc<RefCell<TreeNode>>>,
        ) -> bool {
            match (left, right) {
                // Both nodes are None - symmetric
                (None, None) => true,
                // One node is None - not symmetric
                (None, Some(_)) | (Some(_), None) => false,
                // Both nodes exist - check values and recurse
                (Some(l), Some(r)) => {
                    let l_node = l.borrow();
                    let r_node = r.borrow();

                    if l_node.val != r_node.val {
                        return false;
                    }

                    // Recursively check: left's left with right's right
                    // and left's right with right's left (mirror pattern)
                    is_mirror(&l_node.left, &r_node.right)
                        && is_mirror(&l_node.right, &r_node.left)
                }
            }
        }

        match root {
            Some(node) => {
                let node = node.borrow();
                is_mirror(&node.left, &node.right)
            }
            None => true,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_symmetric_tree() {
        // Example 1: Symmetric tree
        //       1
        //      / \
        //     2   2
        //    / \ / \
        //   3  4 4  3
        let root = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode {
                val: 2,
                left: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
                right: Some(Rc::new(RefCell::new(TreeNode::new(4)))),
            }))),
            right: Some(Rc::new(RefCell::new(TreeNode {
                val: 2,
                left: Some(Rc::new(RefCell::new(TreeNode::new(4)))),
                right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
            }))),
        })));

        assert_eq!(Solution::is_symmetric(root), true);
    }

    #[test]
    fn test_not_symmetric_tree() {
        // Example 2: Not symmetric
        //       1
        //      / \
        //     2   2
        //      \   \
        //       3   3
        let root = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode {
                val: 2,
                left: None,
                right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
            }))),
            right: Some(Rc::new(RefCell::new(TreeNode {
                val: 2,
                left: None,
                right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
            }))),
        })));

        assert_eq!(Solution::is_symmetric(root), false);
    }
}

Go

symmetric_tree_dfs.go

package main

import "fmt"

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

// IsSymmetricDFS checks if a binary tree is symmetric using DFS recursion.
//
// Time Complexity: O(n) - visit each node once
// Space Complexity: O(h) - recursion stack, where h is height
func isSymmetricDFS(root *TreeNode) bool {
  return isMirror(root, root)
}

// isMirror checks if two subtrees are mirrors of each other.
func isMirror(left, right *TreeNode) bool {
  // Both nodes are nil - symmetric
  if left == nil && right == nil {
    return true
  }

  // One node is nil or values differ - not symmetric
  if left == nil || right == nil {
    return false
  }
  if left.Val != right.Val {
    return false
  }

  // Recursively check: left's left with right's right
  // and left's right with right's left (mirror pattern)
  return isMirror(left.Left, right.Right) &&
    isMirror(left.Right, right.Left)
}

func main() {
  // Example 1: Symmetric tree
  //       1
  //      / \
  //     2   2
  //    / \ / \
  //   3  4 4  3
  root1 := &TreeNode{Val: 1}
  root1.Left = &TreeNode{Val: 2}
  root1.Right = &TreeNode{Val: 2}
  root1.Left.Left = &TreeNode{Val: 3}
  root1.Left.Right = &TreeNode{Val: 4}
  root1.Right.Left = &TreeNode{Val: 4}
  root1.Right.Right = &TreeNode{Val: 3}
  fmt.Println(isSymmetricDFS(root1)) // true

  // Example 2: Not symmetric
  //       1
  //      / \
  //     2   2
  //      \   \
  //       3   3
  root2 := &TreeNode{Val: 1}
  root2.Left = &TreeNode{Val: 2}
  root2.Right = &TreeNode{Val: 2}
  root2.Left.Right = &TreeNode{Val: 3}
  root2.Right.Right = &TreeNode{Val: 3}
  fmt.Println(isSymmetricDFS(root2)) // false
}

Approach 2: BFS Iterative

🎯 Interview Favourite

Use a queue to process node pairs level by level. Instead of recursion, explicitly maintain a queue of (left, right) pairs to compare, checking the mirror property iteratively.

This approach avoids recursion entirely and may perform better with very deep or unbalanced trees (reducing stack overflow risk).

⏱ Time O(n) Visit each node once 💾 Space O(w) Queue width at widest level

Step-by-step Example

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

After initialization: queue = [(root.left, root.right)] = [(node 2, node 2)]

Step	Queue	Action
1	[(2, 2)]	Values match, enqueue children in mirror order
2	[(3, 3), (4, 4)]	Both pairs have matching values, enqueue their children
3	[] (all leaf children are null pairs)	All null pairs continue, queue empties
4	Done	Return true (no mismatches found)

Pseudocode

function isSymmetricBFS(root):
    if root is null:
        return true
    queue = [(root.left, root.right)]
    while queue is not empty:
        left, right = queue.dequeue()
        if left is null and right is null:
            continue
        if left is null or right is null:
            return false
        if left.val != right.val:
            return false
        queue.enqueue((left.left, right.right))
        queue.enqueue((left.right, right.left))
    return true

Solution Code

Python

symmetric_tree_bfs.py

from typing import Optional
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_symmetric_bfs(root: Optional[TreeNode]) -> bool:
    """
    Check if a binary tree is symmetric using BFS with a queue.

    Time Complexity: O(n) - visit each node once
    Space Complexity: O(w) - queue width, where w is max nodes at any level
    """
    if not root:
        return True

    queue = deque([(root.left, root.right)])

    while queue:
        left, right = queue.popleft()

        # Both nodes are None - continue (symmetric so far)
        if not left and not right:
            continue

        # One node is None or values differ - not symmetric
        if not left or not right:
            return False
        if left.val != right.val:
            return False

        # Add pairs for next level: left's left with right's right
        # and left's right with right's left (mirror pattern)
        queue.append((left.left, right.right))
        queue.append((left.right, right.left))

    return True


# Test cases
if __name__ == "__main__":
    # Example 1: Symmetric tree
    #       1
    #      / \
    #     2   2
    #    / \ / \
    #   3  4 4  3
    root1 = TreeNode(1)
    root1.left = TreeNode(2)
    root1.right = TreeNode(2)
    root1.left.left = TreeNode(3)
    root1.left.right = TreeNode(4)
    root1.right.left = TreeNode(4)
    root1.right.right = TreeNode(3)
    print(is_symmetric_bfs(root1))  # True

    # Example 2: Not symmetric
    #       1
    #      / \
    #     2   2
    #      \   \
    #       3   3
    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.right = TreeNode(2)
    root2.left.right = TreeNode(3)
    root2.right.right = TreeNode(3)
    print(is_symmetric_bfs(root2))  # False

    # Example 3: Single node
    root3 = TreeNode(1)
    print(is_symmetric_bfs(root3))  # True

C++

symmetric_tree_bfs.cpp

#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:
    /**
     * Check if a binary tree is symmetric using BFS with a queue.
     *
     * Time Complexity: O(n) - visit each node once
     * Space Complexity: O(w) - queue width, where w is max nodes at any level
     */
    bool isSymmetric(TreeNode* root) {
        if (!root) {
            return true;
        }

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

        while (!q.empty()) {
            auto [left, right] = q.front();
            q.pop();

            // Both nodes are null - continue (symmetric so far)
            if (!left && !right) {
                continue;
            }

            // One node is null or values differ - not symmetric
            if (!left || !right) {
                return false;
            }
            if (left->val != right->val) {
                return false;
            }

            // Add pairs for next level: left's left with right's right
            // and left's right with right's left (mirror pattern)
            q.push({left->left, right->right});
            q.push({left->right, right->left});
        }

        return true;
    }
};

// Test cases
int main() {
    Solution sol;

    // Example 1: Symmetric tree
    //       1
    //      / \
    //     2   2
    //    / \ / \
    //   3  4 4  3
    TreeNode* root1 = new TreeNode(1);
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(2);
    root1->left->left = new TreeNode(3);
    root1->left->right = new TreeNode(4);
    root1->right->left = new TreeNode(4);
    root1->right->right = new TreeNode(3);
    cout << (sol.isSymmetric(root1) ? "true" : "false") << endl; // true

    // Example 2: Not symmetric
    //       1
    //      / \
    //     2   2
    //      \   \
    //       3   3
    TreeNode* root2 = new TreeNode(1);
    root2->left = new TreeNode(2);
    root2->right = new TreeNode(2);
    root2->left->right = new TreeNode(3);
    root2->right->right = new TreeNode(3);
    cout << (sol.isSymmetric(root2) ? "true" : "false") << endl; // false

    // Example 3: Single node
    TreeNode* root3 = new TreeNode(1);
    cout << (sol.isSymmetric(root3) ? "true" : "false") << endl; // true

    return 0;
}

Java

symmetric_tree_bfs.java

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

public class SymmetricTreeBFS {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * Check if a binary tree is symmetric using BFS with a queue.
     *
     * Time Complexity: O(n) - visit each node once
     * Space Complexity: O(w) - queue width, where w is max nodes at any level
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode[]> queue = new LinkedList<>();
        queue.offer(new TreeNode[]{root.left, root.right});

        while (!queue.isEmpty()) {
            TreeNode[] pair = queue.poll();
            TreeNode left = pair[0];
            TreeNode right = pair[1];

            // Both nodes are null - continue (symmetric so far)
            if (left == null && right == null) {
                continue;
            }

            // One node is null or values differ - not symmetric
            if (left == null || right == null) {
                return false;
            }
            if (left.val != right.val) {
                return false;
            }

            // Add pairs for next level: left's left with right's right
            // and left's right with right's left (mirror pattern)
            queue.offer(new TreeNode[]{left.left, right.right});
            queue.offer(new TreeNode[]{left.right, right.left});
        }

        return true;
    }

    // Test cases
    public static void main(String[] args) {
        SymmetricTreeBFS sol = new SymmetricTreeBFS();

        // Example 1: Symmetric tree
        //       1
        //      / \
        //     2   2
        //    / \ / \
        //   3  4 4  3
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(2);
        root1.left.left = new TreeNode(3);
        root1.left.right = new TreeNode(4);
        root1.right.left = new TreeNode(4);
        root1.right.right = new TreeNode(3);
        System.out.println(sol.isSymmetric(root1)); // true

        // Example 2: Not symmetric
        //       1
        //      / \
        //     2   2
        //      \   \
        //       3   3
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(2);
        root2.left.right = new TreeNode(3);
        root2.right.right = new TreeNode(3);
        System.out.println(sol.isSymmetric(root2)); // false

        // Example 3: Single node
        TreeNode root3 = new TreeNode(1);
        System.out.println(sol.isSymmetric(root3)); // true
    }
}

JavaScript

symmetric_tree_bfs.js

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

function isSymmetricBFS(root) {
    /**
     * Check if a binary tree is symmetric using BFS with a queue.
     *
     * Time Complexity: O(n) - visit each node once
     * Space Complexity: O(w) - queue width, where w is max nodes at any level
     */
    if (!root) {
        return true;
    }

    const queue = [[root.left, root.right]];

    while (queue.length > 0) {
        const [left, right] = queue.shift();

        // Both nodes are null - continue (symmetric so far)
        if (!left && !right) {
            continue;
        }

        // One node is null or values differ - not symmetric
        if (!left || !right) {
            return false;
        }
        if (left.val !== right.val) {
            return false;
        }

        // Add pairs for next level: left's left with right's right
        // and left's right with right's left (mirror pattern)
        queue.push([left.left, right.right]);
        queue.push([left.right, right.left]);
    }

    return true;
}

// Test cases
if (require.main === module) {
    // Example 1: Symmetric tree
    //       1
    //      / \
    //     2   2
    //    / \ / \
    //   3  4 4  3
    const root1 = new TreeNode(1);
    root1.left = new TreeNode(2);
    root1.right = new TreeNode(2);
    root1.left.left = new TreeNode(3);
    root1.left.right = new TreeNode(4);
    root1.right.left = new TreeNode(4);
    root1.right.right = new TreeNode(3);
    console.log(isSymmetricBFS(root1)); // true

    // Example 2: Not symmetric
    //       1
    //      / \
    //     2   2
    //      \   \
    //       3   3
    const root2 = new TreeNode(1);
    root2.left = new TreeNode(2);
    root2.right = new TreeNode(2);
    root2.left.right = new TreeNode(3);
    root2.right.right = new TreeNode(3);
    console.log(isSymmetricBFS(root2)); // false

    // Example 3: Single node
    const root3 = new TreeNode(1);
    console.log(isSymmetricBFS(root3)); // true
}

module.exports = isSymmetricBFS;

Rust

symmetric_tree_bfs.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

pub struct Solution;

impl Solution {
    /// Check if a binary tree is symmetric using BFS with a queue.
    ///
    /// Time Complexity: O(n) - visit each node once
    /// Space Complexity: O(w) - queue width, where w is max nodes at any level
    pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        match root {
            None => true,
            Some(node) => {
                let node = node.borrow();
                let mut queue: VecDeque<(
                    Option<Rc<RefCell<TreeNode>>>,
                    Option<Rc<RefCell<TreeNode>>>,
                )> = VecDeque::new();

                queue.push_back((node.left.clone(), node.right.clone()));

                while let Some((left_opt, right_opt)) = queue.pop_front() {
                    match (left_opt, right_opt) {
                        // Both nodes are None - continue (symmetric so far)
                        (None, None) => continue,
                        // One node is None - not symmetric
                        (None, Some(_)) | (Some(_), None) => return false,
                        // Both nodes exist - check values and enqueue next level
                        (Some(l), Some(r)) => {
                            let l_node = l.borrow();
                            let r_node = r.borrow();

                            if l_node.val != r_node.val {
                                return false;
                            }

                            // Add pairs for next level: left's left with right's right
                            // and left's right with right's left (mirror pattern)
                            queue.push_back((l_node.left.clone(), r_node.right.clone()));
                            queue.push_back((l_node.right.clone(), r_node.left.clone()));
                        }
                    }
                }

                true
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_symmetric_tree() {
        // Example 1: Symmetric tree
        //       1
        //      / \
        //     2   2
        //    / \ / \
        //   3  4 4  3
        let root = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode {
                val: 2,
                left: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
                right: Some(Rc::new(RefCell::new(TreeNode::new(4)))),
            }))),
            right: Some(Rc::new(RefCell::new(TreeNode {
                val: 2,
                left: Some(Rc::new(RefCell::new(TreeNode::new(4)))),
                right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
            }))),
        })));

        assert_eq!(Solution::is_symmetric(root), true);
    }

    #[test]
    fn test_not_symmetric_tree() {
        // Example 2: Not symmetric
        //       1
        //      / \
        //     2   2
        //      \   \
        //       3   3
        let root = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode {
                val: 2,
                left: None,
                right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
            }))),
            right: Some(Rc::new(RefCell::new(TreeNode {
                val: 2,
                left: None,
                right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
            }))),
        })));

        assert_eq!(Solution::is_symmetric(root), false);
    }

    #[test]
    fn test_single_node() {
        let root = Some(Rc::new(RefCell::new(TreeNode::new(1))));
        assert_eq!(Solution::is_symmetric(root), true);
    }
}

Go

symmetric_tree_bfs.go

package main

import (
  "fmt"
  "sort"
)

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

// IsSymmetricBFS checks if a binary tree is symmetric using BFS with a queue.
//
// Time Complexity: O(n) - visit each node once
// Space Complexity: O(w) - queue width, where w is max nodes at any level
func isSymmetricBFS(root *TreeNode) bool {
  if root == nil {
    return true
  }

  queue := [][2]*TreeNode{
    {root.Left, root.Right},
  }

  for len(queue) > 0 {
    pair := queue[0]
    queue = queue[1:]

    left, right := pair[0], pair[1]

    // Both nodes are nil - continue (symmetric so far)
    if left == nil && right == nil {
      continue
    }

    // One node is nil or values differ - not symmetric
    if left == nil || right == nil {
      return false
    }
    if left.Val != right.Val {
      return false
    }

    // Add pairs for next level: left's left with right's right
    // and left's right with right's left (mirror pattern)
    queue = append(queue, [2]*TreeNode{left.Left, right.Right})
    queue = append(queue, [2]*TreeNode{left.Right, right.Left})
  }

  return true
}

func main() {
  // Example 1: Symmetric tree
  //       1
  //      / \
  //     2   2
  //    / \ / \
  //   3  4 4  3
  root1 := &TreeNode{Val: 1}
  root1.Left = &TreeNode{Val: 2}
  root1.Right = &TreeNode{Val: 2}
  root1.Left.Left = &TreeNode{Val: 3}
  root1.Left.Right = &TreeNode{Val: 4}
  root1.Right.Left = &TreeNode{Val: 4}
  root1.Right.Right = &TreeNode{Val: 3}
  fmt.Println(isSymmetricBFS(root1)) // true

  // Example 2: Not symmetric
  //       1
  //      / \
  //     2   2
  //      \   \
  //       3   3
  root2 := &TreeNode{Val: 1}
  root2.Left = &TreeNode{Val: 2}
  root2.Right = &TreeNode{Val: 2}
  root2.Left.Right = &TreeNode{Val: 3}
  root2.Right.Right = &TreeNode{Val: 3}
  fmt.Println(isSymmetricBFS(root2)) // false

  // Example 3: Single node
  root3 := &TreeNode{Val: 1}
  fmt.Println(isSymmetricBFS(root3)) // true
}

Common mistakes

Watch for these pitfalls

• Wrong mirror pairing: Comparing left.left with right.left instead of right.right. The mirror property requires cross-pairing.
• Forgetting null checks: A tree with missing children on only one side is not symmetric. Always check for null mismatches.
• Modifying the tree: Some solutions try to destructively mark visited nodes. This breaks the original tree. Use a separate comparison structure instead.
• Stack overflow on deep trees: Very deep trees can exhaust the call stack in DFS. BFS is safer for unbalanced trees.

Key insights for interviews

Trade-offs to discuss

• DFS vs. BFS: DFS is more elegant and concise; BFS is more iterative and safer for deep trees. Mention both when discussing the solution.
• Null handling: Symmetry requires checking both value equality and structure matching. A null on one side but not the other breaks symmetry.
• Early termination: Both solutions return false immediately upon detecting a mismatch, avoiding unnecessary traversals.
• Space usage: DFS uses call stack (height-bound); BFS uses explicit queue (width-bound). On a balanced tree, both are similar; on a skewed tree, BFS can be better.
• Related problem: Compare with #100 (Same Tree), which checks if two trees are identical, not mirrored. The key difference is the pairing logic.

Related Problems

• Same Tree ↗ Easy #100
• Binary Tree Level Order Traversal ↗ Medium #102
• Maximum Depth of Binary Tree ↗ Easy #104
• Minimum Depth of Binary Tree ↗ Easy #111

Interview Tips

Key trade-offs to discuss

• Time vs. space trade-offs between approaches
• Handling edge cases (empty inputs, single elements, duplicates)
• Optimization opportunities and when they matter
• Follow-up variations and constraint changes

← Previous
#100 Same Tree Next
#102 Binary Tree Level Order Traversal →