Leetcode 101. Symmetric Tree

Problem Explanation

The problem is basically asking us to check if a given binary tree is symmetric around its center root. In other words, if we were to fold the tree in half from the top, both sides should look exactly the same. This is also often referred to as a mirror image. The binary tree is represented in an array-like structure where null values represent gaps in the tree.

For example, let's consider the following binary tree:

1
2
3    1
4   / \
5  2   2
6 / \ / \
73  4 4  3

This is represented as [1,2,2,3,4,4,3], and we can see that if we fold it along the center root, both sides mirror each other.

Approach

One way to solve this problem is by using recursion. Particularly, a depth-first search (DFS) is quite suitable for this task because it visits all the nodes depth wise along the longest path from the root down to the farthest leaf node, before backtracking and exploring the next branch.

The key insight is to start the recursion from the root node itself. From there, we recursively compare the left side of the left subtree with the right side of the right subtree and vice versa. This is done by comparing the node values (they should be equal) and running similar checks on every corresponding pair of nodes in the left and right subtrees.

Let's step through an example to clarify this:

For the above binary tree example, we start at the root node (value 1). We pass this node itself to the recursive function. Since both nodes are the same, the comparison passes.

Next, we recursively check the left child of the left subtree (value 2) and the right child of the right subtree (also value 2). These values are equal, so the comparison passes.

We continue this pattern, now comparing the left child of the first node (value 3) with the right child of the second node (value 3), and so on.

Python Solution

1
2python
3class Solution:
4    def isSymmetric(self, root):
5        if root is None:
6            return True
7        else:
8            return self.isMirror(root.left, root.right)
9
10    def isMirror(self, left, right):
11        if left is None or right is None:
12            return left == right
13        if left.val != right.val:
14            return False
15        else:
16            return self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)

Java Solution

1
2java
3public class Solution {
4    public boolean isSymmetric(TreeNode root) {
5        return isMirror(root, root);
6    }
7
8    public boolean isMirror(TreeNode t1, TreeNode t2) {
9        if (t1 == null && t2 == null) return true;
10        if (t1 == null || t2 == null) return false;
11        return (t1.val == t2.val)
12                && isMirror(t1.right, t2.left)
13                && isMirror(t1.left, t2.right);
14    }
15}

JavaScript Solution

1
2javascript
3var isSymmetric = function(root) {
4    return isMirror(root, root);
5};
6
7function isMirror(t1, t2) {
8    if (t1 == null && t2 == null) return true;
9    if (t1 == null || t2 == null) return false;
10    return (t1.val == t2.val)
11        && isMirror(t1.right, t2.left)
12        && isMirror(t1.left, t2.right);
13}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool isSymmetric(TreeNode* root) {
6        return isMirror(root, root);
7    }
8
9    bool isMirror(TreeNode* t1, TreeNode* t2) {
10        if (t1 == nullptr && t2 == nullptr) return true;
11        if (t1 == nullptr || t2 == nullptr) return false;
12        return (t1->val == t2->val)
13            && isMirror(t1->right, t2->left)
14            && isMirror(t1->left, t2->right);
15    }
16};

C# Solution

1
2csharp
3public class Solution {
4    public bool IsSymmetric(TreeNode root) {
5    return IsMirror(root, root);
6    }
7
8    public bool IsMirror(TreeNode t1, TreeNode t2) {
9        if (t1 == null && t2 == null) return true;
10        if (t1 == null || t2 == null) return false;
11        return (t1.val == t2.val)
12            && IsMirror(t1.right, t2.left)
13            && IsMirror(t1.left, t2.right);
14    }
15}

The solutions above use the helper function isMirror() to check the mirror condition on the left and right subtree of each node, recursively. It first checks for the base conditions - if both nodes are null, it returns true, if either node is null, it returns false. Then it checks if the two values are equal and makes a recursive call on the right subtree of the first node and the left subtree of the second node, and vice versa. If all conditions pass, the function will ultimately return true - meaning the tree is symmetric.Conclusively, it's important to note that these recursive solutions have time complexities of O(n), where n is the number of nodes in the tree. As for space complexity, this also amounts to O(n), specifically in the worst case scenario when the tree is somewhat skewed, resulting in a very high number of recursive calls that are held on the call stack.

Maintaining a good understanding of binary tree-related concepts, which includes recognizing when to utilize different types of tree traversals, is vital to solving this problem. Specifically, the strategy to parallelly traverse a tree can be applied to a range of varying but related problems like same tree validation, subtree checks, and more.

In learning and understanding these solutions, ensure to run the code with varying test scenarios - different binary tree configurations - to ascertain how well you grasp the concept. This hands-on approach will solidify your learning, making it easier to understand related problems and how to utilize specific methodologies in solving them.

Lastly, keep in mind that though binary tree problems might seem daunting at first, consistent practice will make them a lot easier to tackle. Keep encoding!