LeetCode: 101. Symmetric Tree

The Problem

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

Example

Input:  [1,2,2,3,4,4,3]
Output: true

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

bool isSymmetric(TreeNode *left, TreeNode *right){

	if(left == nullptr ) return right == nullptr;
    if(right == nullptr) return false;

	return  left->val == right->val && 
    		isSymmetric(left->left, right->right) &&
		    isSymmetric(left->right, right->left);
}

bool isSymmetric(TreeNode* root) {
	return isSymmetric(root->left, root->right);
}

Let's break down this code step by step so that it's easy to understand:

This code is used to determine whether a given binary tree is symmetric or not. A symmetric binary tree is a tree that can be folded along its center, and the left and right subtrees of each node match each other in structure.

bool isSymmetric(TreeNode *left, TreeNode *right) Function:

This function takes in two pointers, left and right, representing the left and right subtrees of a certain node in the tree.

• The first if statement checks if the left subtree is nullptr (empty). If it is, then it checks whether the right subtree is also nullptr. If both subtrees are empty, the function returns true because an empty subtree is symmetric to another empty subtree.
• The second if statement checks if the right subtree is nullptr. If it is while the left subtree is not nullptr, this means that the tree is not symmetric, so the function returns false.
• If none of the above conditions are met, it means both left and right subtrees are non-empty. The function then checks if the values at the current nodes of the left and right subtrees are the same. Additionally, it recursively checks whether the left subtree of the left node is symmetric to the right subtree of the right node, and vice versa.
• The return statement combines these conditions using logical AND (&&). If all these conditions hold true, the function returns true, indicating that the subtrees are symmetric; otherwise, it returns false.

bool isSymmetric(TreeNode* root) Function:

This function is a wrapper function that checks whether the whole binary tree rooted at root is symmetric.

• It starts by calling the isSymmetric function with the left and right subtrees of the root node. This effectively compares the left and right subtrees to determine if the entire tree is symmetric.
• The result of the comparison is directly returned by this wrapper function.