101 || Symmetric Tree || Leetcode Daily Problem

Problem Link :- leetcode-101

Problem statement

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

Significance of problem

The significance of the "Symmetric Tree" problem lies in its exploration of tree structures and symmetry validation, which mirrors real-world scenarios where hierarchical structures demand meticulous analysis. This problem delves into the core concept of tree symmetry and serves as a fundamental exercise in recursive algorithmic design. By checking whether a binary tree is symmetric around its center, the problem enhances learners' comprehension of tree traversal, node comparison, and recursive strategies.

Furthermore, the problem addresses the symmetry of binary trees, a crucial consideration in various computational applications. This includes hierarchical data representation, syntax tree analysis in parsing, and hierarchical organizational structures in databases. Understanding and validating tree symmetry are essential skills for ensuring accurate and efficient operations in these domains.

Moreover, the problem fosters adaptability in recursive design, as it requires traversing the tree in a manner that mirrors nodes on either side of the center. The recursive approach exemplified in the code solution demonstrates the elegance of recursive algorithms in tackling complex tree structures.

In essence, mastering the "Symmetric Tree" problem not only hones skills in tree traversal and recursive algorithms but also highlights the practical implications of symmetry validation in hierarchical data structures—a skill set crucial for developers navigating diverse computational challenges where accurate representation and analysis of hierarchical relationships are paramount.

Easiest Explanation

In this problem, we're going to look at a special kind of tree called a binary tree. A binary tree is made up of nodes, and each node can have up to two child nodes. We call the topmost node the root of the tree.

Now, we're going to check whether this tree is a special kind of tree called a mirror tree. That means that if we drew a line down the center of the tree from the root, the left and right sides would be exactly the same. It's kind of like looking in a mirror - if you hold a mirror up to the left side of your face, you'll see the right side of your face reflected back to you.

So, we want to check whether this tree is a mirror tree. To do that, we'll look at the left and right sides of the tree and see if they're the same. If they are, then the tree is a mirror tree! But if they're not the same, then it's not a mirror tree.

To check whether the left and right sides of the tree are the same, we'll start at the root and compare the left and right child nodes. Then, we'll compare the left child's left child with the right child's right child, and the left child's right child with the right child's left child. We'll keep doing this until we reach the bottom of the tree. If all of these pairs of nodes are the same, then the tree is a mirror tree.

So, in summary, we're going to look at a tree and see if it's a mirror tree. We'll do this by comparing the left and right sides of the tree and checking if they're the same. We'll start at the top and compare pairs of nodes all the way down to the bottom. If they're all the same, then the tree is a mirror tree!

I hope that explanation helps! If you find any difficulty in solving, feel free to comment with your doubts.

Python Code :

class Solution:
      def solve(self, l1: TreeNode, l2: TreeNode) -> bool:
          if not l1 and not l2:
              return True
          if not l1 or not l2:
              return False
          if l1.val != l2.val:
              return False
          return self.solve(l1.left, l2.right) and self.solve(l1.right, l2.left)

      def isSymmetric(self, root: TreeNode) -> bool:
          if not root:
              return True
          return self.solve(root.left, root.right)

CPP Code

class Solution {
public:
    bool solve(TreeNode* l1,TreeNode* l2){
        if(l1==NULL && l2==NULL) return true;
        if(l1==NULL || l2==NULL) return false;
        if(l2->val != l1->val) return false;

        return solve(l1->left,l2->right) && solve(l1->right,l2->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(root==NULL)return 1;
        return solve(root->left,root->right);
    }
};
    

Here's how the function works:

1. This code defines a class named Solution.

2. The Solution class contains two functions: "solve" and "isSymmetric".

3. The "solve" function takes in two TreeNode pointers, l1 and l2, which represent the left and right nodes of a binary tree, respectively. The function returns a boolean value.

4. In the "solve" function, if both l1 and l2 are NULL, the function returns true (indicating that the nodes are symmetric).

5. If either l1 or l2 is NULL (but not both), the function returns false (indicating that the nodes are not symmetric).

6. If both l1 and l2 are not NULL, and their values are not equal, the function returns false (indicating that the nodes are not symmetric).

7. If none of the above cases apply, the function recursively calls itself, passing in l1->left and l2->right as well as l1->right and l2->left, and returns the AND logical operator of the two recursive calls. This means that both recursive calls must return true in order for the "solve" function to return true (indicating that the nodes are symmetric).

8. The "isSymmetric" function takes in a single TreeNode pointer, "root", representing the root of a binary tree. It returns a boolean value.

9. In the "isSymmetric" function, if the root node is NULL, the function returns true (indicating that the tree is symmetric).

10. If the root node is not NULL, the function calls the "solve" function, passing in the root node's left and right nodes as arguments. The function returns the value returned by the "solve" function, indicating whether or not the tree is symmetric.

Learning Outcomes

Solving the "Symmetric Tree" problem yields valuable learning outcomes that contribute to a deeper understanding of tree structures and recursive algorithmic design. Firstly, learners gain proficiency in tree traversal, comprehending how to navigate binary trees symmetrically to compare corresponding nodes effectively. This skill is foundational for various tree-based algorithms and forms the basis for more complex tree-related problems.

Secondly, the problem enhances learners' understanding of recursion, showcasing its power in dealing with intricate tree structures. The recursive approach employed in the code solution illustrates how breaking down a complex problem into smaller, more manageable subproblems can lead to an elegant and efficient solution.

Moreover, the problem cultivates a keen eye for symmetry validation, a skill essential in various computational domains. The ability to discern and verify symmetry in hierarchical structures, such as syntax trees or organizational hierarchies, is crucial for ensuring accurate representation and analysis.

Furthermore, learners develop adaptability in handling different tree configurations. The problem's requirement to validate symmetry around the center prompts learners to consider various tree structures, fostering a versatile mindset for addressing diverse tree-related challenges.

Conclusion

In conclusion, solving the "Symmetric Tree" problem instills essential skills in tree traversal, recursive algorithms, and symmetry validation. The ability to check whether a binary tree is symmetric around its center is foundational for diverse tree-related challenges. Mastering this problem hones one's proficiency in navigating and analyzing hierarchical structures, providing a solid basis for tackling more complex problems in computational scenarios.

Overall, the "Symmetric Tree" problem contributes to a well-rounded skill set essential for effective algorithmic problem-solving in the realm of tree structures and recursive design.

Stay up-to-date with our latest content by subscribing to our channel! Don't miss out on our next video - make sure to subscribe today.