{"id":705,"date":"2024-10-10T13:38:16","date_gmt":"2024-10-10T08:08:16","guid":{"rendered":"https:\/\/codexplained.in\/?p=705"},"modified":"2025-11-24T15:59:46","modified_gmt":"2025-11-24T10:29:46","slug":"check-if-binary-tree-is-symmetric","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=705","title":{"rendered":"Check if Binary Tree is Symmetric"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Define the structure for a tree node.\nstruct TreeNode {\n    int val;\n    struct TreeNode *left;\n    struct TreeNode *right;\n};\n\n\/\/ Function to create a new tree node.\nstruct TreeNode* createNode(int value) {\n    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n    newNode->val = value;\n    newNode->left = NULL;\n    newNode->right = NULL;\n    return newNode;\n}\n\n\/\/ Function to check if two trees are mirrors of each other.\nint areMirrors(struct TreeNode* tree1, struct TreeNode* tree2) {\n    \/\/ If both nodes are NULL, they are mirrors.\n    if (tree1 == NULL && tree2 == NULL) return 1;\n    \n    \/\/ If one of them is NULL, they are not mirrors.\n    if (tree1 == NULL || tree2 == NULL) return 0;\n    \n    \/\/ Check if the values of the nodes are equal and if the left subtree of one tree\n    \/\/ is a mirror of the right subtree of the other tree and vice versa.\n    return (tree1->val == tree2->val) &&\n           areMirrors(tree1->left, tree2->right) &&\n           areMirrors(tree1->right, tree2->left);\n}\n\n\/\/ Function to check if a tree is symmetric.\nint isSymmetric(struct TreeNode* root) {\n    \/\/ An empty tree is symmetric.\n    if (root == NULL) return 1;\n    \n    \/\/ Check if the left and right subtrees are mirrors.\n    return areMirrors(root->left, root->right);\n}\n\n\/\/ Main function to test the code.\nint main() {\n    \/\/ Create a symmetric tree.\n    struct TreeNode* root = createNode(1);\n    root->left = createNode(2);\n    root->right = createNode(2);\n    root->left->left = createNode(3);\n    root->left->right = createNode(4);\n    root->right->left = createNode(4);\n    root->right->right = createNode(3);\n\n    \/\/ Check if the tree is symmetric.\n    if (isSymmetric(root)) {\n        printf("The tree is symmetric.\\n");\n    } else {\n        printf("The tree is not symmetric.\\n");\n    }\n\n    \/\/ Free the allocated memory (optional but good practice).\n    free(root->left->left);\n    free(root->left->right);\n    free(root->right->left);\n    free(root->right->right);\n    free(root->left);\n    free(root->right);\n    free(root);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation<\/h3>\n\n\n\n
    \n
  1. TreeNode Structure<\/strong>: We define a TreeNode<\/code> structure that holds a value val<\/code> and pointers to the left and right children.<\/li>\n\n\n\n
  2. createNode Function<\/strong>: This function allocates memory for a new node and initializes it with a given value.<\/li>\n\n\n\n
  3. areMirrors Function<\/strong>: This recursive function checks if two trees are mirror images of each other:\n
      \n
    • If both nodes are NULL<\/code>, return 1<\/code> (true).<\/li>\n\n\n\n
    • If one is NULL<\/code> and the other isn’t, return 0<\/code> (false).<\/li>\n\n\n\n
    • Check if the node values are equal, and the left subtree of one is a mirror of the right subtree of the other.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • isSymmetric Function<\/strong>: This function checks if the entire tree is symmetric by calling areMirrors<\/code> with the left and right children of the root.<\/li>\n\n\n\n
    • Main Function<\/strong>: This creates a simple symmetric tree, checks its symmetry, and prints the result.<\/li>\n<\/ol>\n\n\n\n
      Output<\/h3>\n\n\n\n
      When the program runs with the example tree, the output will be:<\/p>\n\n\n\n
      The tree is symmetric.\n<\/code><\/pre>\n\n\n\n
      If you modify the tree structure in the main function (e.g., remove a node), it will print:<\/p>\n\n\n\n
      The tree is not symmetric.\n<\/code><\/pre>\n\n\n\n
      Memory Management<\/h3>\n\n\n\n
      In this example, memory is freed for each allocated node at the end. It’s a good practice, though the program will automatically free memory on termination in many cases. However, explicitly freeing memory is important in larger applications to prevent memory leaks.<\/p>\n