Determining Symmetric Trees: A Recursive Approach

Introduction

In this blog post, we will discuss the problem of determining whether a given binary tree is symmetric or not. A binary tree is considered symmetric if it is a mirror image of itself, i.e., if the left and right subtrees are identical.

Problem Statement

Given the root of a binary tree, we need to check whether it is a symmetric tree.

Data Structure Used

We will be using the TreeNode data structure to represent the nodes of the binary tree. Each TreeNode has a value and pointers to its left and right child nodes.

Algorithmic Approach

To solve this problem, we will use a recursive approach. We will define a helper function treeCheck() that takes in two nodes as arguments and checks if they are symmetric. The base case for the recursion is when both nodes are null, in which case we return true. If either one of the nodes is null or their values are different, we return false.

The recursive step involves comparing the left child of the left node with the right child of the right node, and the right child of the left node with the left child of the right node. We recursively call treeCheck() with these pairs of nodes and return the logical AND of the results.

bool isSymmetric(TreeNode *root) {
    if (root == NULL) {
        return true;
    }
    return treeCheck(root->left, root->right);
}

bool treeCheck(TreeNode *left, TreeNode *right) {
    if (left == NULL && right == NULL)
        return true;
    if (left == NULL || right == NULL || left->val != right->val)
        return false;
    return treeCheck(left->left, right->right) && treeCheck(left->right, right->left);
}

Time Complexity

The time complexity of the algorithm is O(N), where N is the number of nodes in the binary tree. We need to visit each node exactly once to check for symmetry.

Space Complexity

The space complexity of the algorithm is O(H), where H is the height of the binary tree. The recursive calls use the call stack, which requires additional space proportional to the height of the tree.

Conclusion

In this blog post, I have explored the problem of determining whether a binary tree is symmetric or not. We discussed the algorithmic approach using recursion and analyzed the time and space complexity of the solution. The provided code snippet demonstrates a simple and efficient solution to solve the symmetric tree problem.

Symmetric Tree - Check if a Binary Tree is Symmetric