Check if Tree is Symmetric 🎯

Welcome to this comprehensive guide on checking if a tree is symmetric! In this lesson, we'll delve into the world of data structures and algorithms, focusing on trees and symmetry. By the end of this tutorial, you'll have a solid understanding of how to check if a tree is symmetric, and you'll be able to apply this knowledge to various real-world projects.

Table of Contents 📝

Understanding Trees
- 1.1. Introduction to Trees
- 1.2. Types of Trees
- 1.3. Tree Traversal Methods
Symmetric Trees
- 2.1. Definition of Symmetric Trees
- 2.2. Importance of Symmetric Trees
Checking if a Tree is Symmetric
- 3.1. Algorithm Overview
- 3.2. Recursive Solution
- 3.3. Iterative Solution
Code Examples
- 4.1. Recursive Solution in Python
- 4.2. Iterative Solution in Java
Quiz

1. Understanding Trees 📝

1.1. Introduction to Trees

A tree is a collection of nodes where each node is connected to at most one parent node and any number of child nodes. The root node is the topmost node in the tree with no parent node. Trees are used to represent hierarchical structures, such as a family tree or a file system.

1.2. Types of Trees

Binary Trees: A binary tree is a tree in which each node has at most two children, called the left child and the right child.
AVL Trees: An AVL tree is a self-balancing binary search tree, where the height of the left and right subtrees of any node differ by at most one.
B-Trees: A B-tree is a self-balancing multi-way search tree, allowing each node to have more than two children.

1.3. Tree Traversal Methods

Inorder Traversal: Traverses the left subtree, then the current node, and finally the right subtree.
Preorder Traversal: Traverses the current node, then the left subtree, and finally the right subtree.
Postorder Traversal: Traverses the left subtree, then the right subtree, and finally the current node.

2. Symmetric Trees 📝

2.1. Definition of Symmetric Trees

A binary tree is symmetric if the left subtree of its root is identical to the right subtree, mirrored about the root. In other words, if you swap the left and right subtrees of every node, the tree should remain the same.

2.2. Importance of Symmetric Trees

Symmetric trees have applications in data compression, image processing, and cryptography. They are particularly useful in algorithms that require balanced trees, as they maintain balance without the need for re-balancing operations.

3. Checking if a Tree is Symmetric 📝

3.1. Algorithm Overview

The algorithm to check if a tree is symmetric involves recursively comparing the left subtree of the root with the right subtree of the root. If the left and right subtrees are equal (i.e., have the same nodes in the same order), then the tree is symmetric.

3.2. Recursive Solution 💡

python

def is_symmetric(root):
    return is_same_tree(root.left, root.right)

def is_same_tree(t1, t2):
    if not t1 and not t2:
        return True
    if not t1 or not t2:
        return False
    return (t1.val == t2.val and
            is_same_tree(t1.left, t2.right) and
            is_same_tree(t1.right, t2.left))

3.3. Iterative Solution 💡

java

public boolean isSymmetric(TreeNode root) {
    Queue<TreeNode> queueLeft = new LinkedList<>();
    Queue<TreeNode> queueRight = new LinkedList<>();
    queueLeft.add(root.left);
    queueRight.add(root.right);
    while (!queueLeft.isEmpty() && !queueRight.isEmpty()) {
        TreeNode leftNode = queueLeft.poll();
        TreeNode rightNode = queueRight.poll();
        if (leftNode == null && rightNode == null) continue;
        if (leftNode == null || rightNode == null ||
                leftNode.val != rightNode.val) return false;
        queueLeft.add(leftNode.left);
        queueLeft.add(leftNode.right);
        queueRight.add(rightNode.right);
        queueRight.add(rightNode.left);
    }
    return true;
}

4. Quiz 📝

:::quiz Question: Which of the following trees is symmetric?

     1
    /   \
   2     2
  / \     / \
 3   4   4   3

A: The given tree is symmetric. B: The given tree is not symmetric. Correct: A Explanation: If you swap the left and right subtrees of the root, the tree remains the same.