Solution 1 - Recursive Mirror Check

Define a helper function that takes two nodes and checks if they are mirrors of each other. Two nodes are mirrors if both are None, or if their values are equal and the left child of one mirrors the right child of the other, and vice versa. Call the helper with root, root to check the full tree.

TimeComplexity: O(n)

SpaceComplexity: O(h)

""" 0101.1 - Symmetric Tree - Solution 1 - Recursive Mirror Check """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        """Symmetric Tree Function"""

        def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
            if not t1 and not t2:
                return True
            if not t1 or not t2:
                return False
            return (
                t1.val == t2.val
                and isMirror(t1.left, t2.right)
                and isMirror(t1.right, t2.left)
            )

        return isMirror(root, root)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    root1 = TreeNode(
        1,
        TreeNode(2, TreeNode(3), TreeNode(4)),
        TreeNode(2, TreeNode(4), TreeNode(3)),
    )
    print(Solution().isSymmetric(root1))  # True

    root2 = TreeNode(
        1,
        TreeNode(2, None, TreeNode(3)),
        TreeNode(2, None, TreeNode(3)),
    )
    print(Solution().isSymmetric(root2))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0101.1 - Symmetric Tree - Solution 1 - Recursive Mirror Check */

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

class Solution {
    /** Symmetric Tree Function */
    isSymmetric(root) {
        const isMirror = (t1, t2) => {
            if (!t1 && !t2) return true;
            if (!t1 || !t2) return false;
            return (
                t1.val === t2.val &&
                isMirror(t1.left, t2.right) &&
                isMirror(t1.right, t2.left)
            );
        };
        return isMirror(root, root);
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    const root1 = new TreeNode(
        1,
        new TreeNode(2, new TreeNode(3), new TreeNode(4)),
        new TreeNode(2, new TreeNode(4), new TreeNode(3)),
    );
    console.log(new Solution().isSymmetric(root1)); // true

    const root2 = new TreeNode(
        1,
        new TreeNode(2, null, new TreeNode(3)),
        new TreeNode(2, null, new TreeNode(3)),
    );
    console.log(new Solution().isSymmetric(root2)); // false
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0101.1 - Symmetric Tree - Solution 1 - Recursive Mirror Check */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class TreeNode {
    constructor(
        public val: number = 0,
        public left: TreeNode | null = null,
        public right: TreeNode | null = null,
    ) {}
}

class Solution {
    /** Symmetric Tree Function */
    isSymmetric(root: TreeNode | null): boolean {
        const isMirror = (t1: TreeNode | null, t2: TreeNode | null): boolean => {
            if (!t1 && !t2) return true;
            if (!t1 || !t2) return false;
            return (
                t1.val === t2.val &&
                isMirror(t1.left, t2.right) &&
                isMirror(t1.right, t2.left)
            );
        };

        return isMirror(root, root);
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    const root1 = new TreeNode(
        1,
        new TreeNode(2, new TreeNode(3), new TreeNode(4)),
        new TreeNode(2, new TreeNode(4), new TreeNode(3)),
    );
    console.log(new Solution().isSymmetric(root1)); // true

    const root2 = new TreeNode(
        1,
        new TreeNode(2, null, new TreeNode(3)),
        new TreeNode(2, null, new TreeNode(3)),
    );
    console.log(new Solution().isSymmetric(root2)); // false
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0101.1 - Symmetric Tree - Solution 1 - Recursive Mirror Check

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

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

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func isMirror(t1 *TreeNode, t2 *TreeNode) bool {
	if t1 == nil || t2 == nil {
		return t1 == t2
	}
	return t1.Val == t2.Val && isMirror(t1.Left, t2.Right) && isMirror(t1.Right, t2.Left)
}

func isSymmetric(root *TreeNode) bool {
	return isMirror(root, root)
}

func testcase() {
	root1 := &TreeNode{
		Val: 1,
		Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}, Right: &TreeNode{Val: 4}},
		Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}, Right: &TreeNode{Val: 3}},
	}
	fmt.Println(isSymmetric(root1)) // true
}

/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0101.1 - Symmetric Tree - Solution 1 - Recursive Mirror Check

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

struct Solution;

impl Solution {
    pub fn is_symmetric(root: &Option<Box<TreeNode>>) -> bool {
        fn is_mirror(a: &Option<Box<TreeNode>>, b: &Option<Box<TreeNode>>) -> bool {
            match (a, b) {
                (None, None) => true,
                (Some(x), Some(y)) => {
                    x.val == y.val && is_mirror(&x.left, &y.right) && is_mirror(&x.right, &y.left)
                }
                _ => false,
            }
        }
        is_mirror(root, root)
    }
}

fn main() {
    let root: Option<Box<TreeNode>> = None;
    println!("{}", Solution::is_symmetric(&root));
}

Solution 2 - Iterative with Queue

Use a queue to compare nodes level by level. Start by enqueuing the root twice. At each step, dequeue two nodes and compare them. If both are None, continue. If only one is None or their values differ, return False. Otherwise, enqueue the children in mirror order: left of first with right of second, and right of first with left of second.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0101.2 - Symmetric Tree - Solution 2 - Iterative with Queue """

#####################################################################################
# Imports
#####################################################################################
from collections import deque
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        """Symmetric Tree Function"""
        queue = deque([root, root])

        while queue:
            t1 = queue.popleft()
            t2 = queue.popleft()

            if not t1 and not t2:
                continue
            if not t1 or not t2:
                return False
            if t1.val != t2.val:
                return False

            queue.append(t1.left)
            queue.append(t2.right)
            queue.append(t1.right)
            queue.append(t2.left)

        return True


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    root1 = TreeNode(
        1,
        TreeNode(2, TreeNode(3), TreeNode(4)),
        TreeNode(2, TreeNode(4), TreeNode(3)),
    )
    print(Solution().isSymmetric(root1))  # True

    root2 = TreeNode(
        1,
        TreeNode(2, None, TreeNode(3)),
        TreeNode(2, None, TreeNode(3)),
    )
    print(Solution().isSymmetric(root2))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0101.2 - Symmetric Tree - Solution 2 - Iterative with Queue */

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

class Solution {
    /** Symmetric Tree Function */
    isSymmetric(root) {
        const queue = [root, root];

        while (queue.length) {
            const t1 = queue.shift();
            const t2 = queue.shift();

            if (!t1 && !t2) continue;
            if (!t1 || !t2) return false;
            if (t1.val !== t2.val) return false;

            queue.push(t1.left, t2.right, t1.right, t2.left);
        }
        return true;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    const root1 = new TreeNode(
        1,
        new TreeNode(2, new TreeNode(3), new TreeNode(4)),
        new TreeNode(2, new TreeNode(4), new TreeNode(3)),
    );
    console.log(new Solution().isSymmetric(root1)); // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0101.2 - Symmetric Tree - Solution 2 - Iterative with Queue */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class TreeNode {
    constructor(
        public val: number = 0,
        public left: TreeNode | null = null,
        public right: TreeNode | null = null,
    ) {}
}

class Solution {
    /** Symmetric Tree Function */
    isSymmetric(root: TreeNode | null): boolean {
        const queue: Array<TreeNode | null> = [root, root];

        while (queue.length) {
            const t1 = queue.shift()!;
            const t2 = queue.shift()!;

            if (!t1 && !t2) continue;
            if (!t1 || !t2) return false;
            if (t1.val !== t2.val) return false;

            queue.push(t1.left, t2.right, t1.right, t2.left);
        }
        return true;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    const root1 = new TreeNode(
        1,
        new TreeNode(2, new TreeNode(3), new TreeNode(4)),
        new TreeNode(2, new TreeNode(4), new TreeNode(3)),
    );
    console.log(new Solution().isSymmetric(root1)); // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0101.2 - Symmetric Tree - Solution 2 - Iterative with Queue

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

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

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func isSymmetric(root *TreeNode) bool {
	queue := []*TreeNode{root, root}

	for len(queue) > 0 {
		t1 := queue[0]
		t2 := queue[1]
		queue = queue[2:]

		if t1 == nil && t2 == nil {
			continue
		}
		if t1 == nil || t2 == nil {
			return false
		}
		if t1.Val != t2.Val {
			return false
		}

		queue = append(queue, t1.Left, t2.Right, t1.Right, t2.Left)
	}
	return true
}

func testcase() {
	root1 := &TreeNode{
		Val: 1,
		Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}, Right: &TreeNode{Val: 4}},
		Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}, Right: &TreeNode{Val: 3}},
	}
	fmt.Println(isSymmetric(root1)) // true
}

/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0101.2 - Symmetric Tree - Solution 2 - Iterative with Queue

use std::collections::VecDeque;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

struct Solution;

impl Solution {
    pub fn is_symmetric(root: Option<Box<TreeNode>>) -> bool {
        let mut queue: VecDeque<Option<Box<TreeNode>>> = VecDeque::new();
        queue.push_back(root.clone());
        queue.push_back(root);

        while let Some(t1) = queue.pop_front() {
            let t2 = queue.pop_front().unwrap();
            match (t1, t2) {
                (None, None) => continue,
                (Some(a), Some(b)) => {
                    if a.val != b.val {
                        return false;
                    }
                    queue.push_back(a.left);
                    queue.push_back(b.right);
                    queue.push_back(a.right);
                    queue.push_back(b.left);
                }
                _ => return false,
            }
        }
        true
    }
}

fn main() {}

0101 - Symmetric Tree

Solution 1 - Recursive Mirror Check

Solution 2 - Iterative with Queue