Understanding and Solving the Symmetric Tree Problem in LeetCode with Java

LeetCode is a popular platform for coding challenges that test your algorithmic and programming skills. One of the common problems you might come across on LeetCode is the Symmetric Tree problem. In this blog, we will delve into the details of the Symmetric Tree problem, understand what it means for a binary tree to be symmetric, and then solve it using Java.

What is the Symmetric Tree Problem?

The Symmetric Tree problem on LeetCode is framed as follows:

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

This problem can be a bit confusing at first, so let’s break it down step by step.

What is a Binary Tree?

Before diving into the Symmetric Tree problem, let’s clarify what a binary tree is. A binary tree is a hierarchical data structure in which each node has at most two children, which are referred to as the left child and the right child. Here’s an example of a simple binary tree:

        1
       / \
      2   2
     / \ / \
    3  4 4  3

In this example, each node has either zero, one, or two children. Node 1 is the root of the tree, and it has two children, nodes 2 and 2. Node 2, in turn, has two children, nodes 3 and 4.

What Does It Mean for a Binary Tree to Be Symmetric?

To understand what it means for a binary tree to be symmetric, let’s look at an example. Consider the following binary tree:

        1
       / \
      2   2
     / \ / \
    3  4 4  3

This tree is symmetric because, if you draw a vertical line through the root node (node 1), the left and right subtrees are mirror images of each other. The left subtree (nodes 2, 3, and 4) is a mirror image of the right subtree (nodes 2, 4, and 3).

Here’s another example:

        1
       / \
      2   2
       \   \
        3   3

This tree is not symmetric because, even though the left and right subtrees have the same structure, they are not mirror images of each other. The left subtree has node 2 and its child node 3, while the right subtree has node 2 and its child node 3. They are not mirror images because the positions of nodes 2 and 3 are different.

In summary, for a binary tree to be symmetric, its left and right subtrees must be mirror images of each other concerning the arrangement of nodes.

How to Solve the Symmetric Tree Problem in Java

Now that we understand what it means for a binary tree to be symmetric, let’s discuss how to solve this problem in Java. We’ll go through two approaches to solving this problem: a recursive approach and an iterative approach.

Recursive Approach

The recursive approach is the most intuitive way to check if a binary tree is symmetric. We can define a recursive function that takes two tree nodes as arguments and checks if they are mirror images of each other. Here’s a step-by-step breakdown of the algorithm:

  1. Define a recursive function isMirror that takes two tree nodes, left and right, as arguments.
  2. The base case for recursion is when both left and right are null. In this case, return true because two null nodes are considered symmetric.
  3. If either left or right is null while the other is not, return false because a null node cannot be a mirror image of a non-null node.
  4. If both left and right are not null, compare their values. If they are not equal, return false because they do not mirror each other.
  5. Recursively call the isMirror function with left‘s left child and right‘s right child and with left‘s right child and right‘s left child. If both recursive calls return true, the tree is symmetric; otherwise, return false.

Now, let’s implement this algorithm in Java code:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class SymmetricTree {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true; // An empty tree is symmetric.
        }
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true; // Two null nodes are symmetric.
        }
        if (left == null || right == null) {
            return false; // One null node and one non-null node are not symmetric.
        }
        if (left.val != right.val) {
            return false; // Nodes with different values are not symmetric.
        }
        // Recursively check the mirror subtrees.
        return isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }
}

Iterative Approach

While the recursive approach is intuitive, it can be implemented iteratively using a queue data structure. In this approach, we maintain two queues, one for the left subtree and one for the right subtree. We enqueue the left child of the left subtree’s nodes into one queue and the right child of the right subtree’s nodes into the other queue. Then, we compare the nodes popped from the two queues to check if they mirror each other. If at any point, the nodes do not mirror each other, we return false. If both queues become empty and we haven’t returned false, the tree is symmetric, and we return true.

Let’s implement this iterative approach in Java code:

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class SymmetricTree {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true; // An empty tree is symmetric.
        }

        Queue<TreeNode> leftQueue = new LinkedList<>();
        Queue<TreeNode> rightQueue = new LinkedList<>();

        leftQueue.add(root.left);
        rightQueue.add(root.right);

        while (!leftQueue.isEmpty() && !rightQueue.isEmpty()) {
            TreeNode leftNode = leftQueue.poll();
            TreeNode rightNode = rightQueue.poll();

            if (leftNode == null && rightNode == null) {
                continue; // Two null nodes are symmetric.
            }
            if (leftNode == null || rightNode == null) {
                return false; // One null node and one non-null node are not symmetric.
            }
            if (leftNode.val != rightNode.val) {
                return false; // Nodes with different values are not symmetric.
            }

            // Enqueue the left child of the left subtree's

 nodes and the right child
            // of the right subtree's nodes.
            leftQueue.add(leftNode.left);
            leftQueue.add(leftNode.right);
            rightQueue.add(rightNode.right);
            rightQueue.add(rightNode.left);
        }

        // If both queues become empty without returning false, the tree is symmetric.
        return true;
    }
}

Testing the Symmetric Tree Solution

To test our Symmetric Tree solution, let’s create some binary trees and check if they are symmetric or not using both the recursive and iterative methods.

Example 1: A Symmetric Tree

Consider the following symmetric binary tree:

        1
       / \
      2   2
     / \ / \
    3  4 4  3

Let’s use our SymmetricTree class to check if it’s symmetric:

public static void main(String[] args) {
    SymmetricTree symmetricTree = new SymmetricTree();
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(2);
    root.left.left = new TreeNode(3);
    root.left.right = new TreeNode(4);
    root.right.left = new TreeNode(4);
    root.right.right = new TreeNode(3);

    boolean isSymmetric = symmetricTree.isSymmetric(root);
    System.out.println("Is the tree symmetric? " + isSymmetric);
}

The expected output should be:

Is the tree symmetric? true

Example 2: A Non-Symmetric Tree

Now, let’s consider a non-symmetric binary tree:

        1
       / \
      2   2
       \   \
        3   3

Using the same code as above to check if it’s symmetric, we should get the following output:

Is the tree symmetric? false

Example 3: An Empty Tree

An empty tree is always symmetric. Let’s test this case:

public static void main(String[] args) {
    SymmetricTree symmetricTree = new SymmetricTree();
    TreeNode root = null; // An empty tree

    boolean isSymmetric = symmetricTree.isSymmetric(root);
    System.out.println("Is the tree symmetric? " + isSymmetric);
}

The expected output should be:

Is the tree symmetric? true

Time and Space Complexity Analysis

Before we conclude, let’s briefly analyze the time and space complexity of our solution.

Time Complexity

Both the recursive and iterative solutions traverse each node in the binary tree exactly once. Therefore, the time complexity of both solutions is O(n), where n is the number of nodes in the tree.

Space Complexity

The space complexity of the recursive solution depends on the height of the binary tree, and in the worst case (a completely unbalanced tree), it can be O(n). This is because the recursive calls are placed on the call stack, and in the worst case, the stack can have n frames.

The space complexity of the iterative solution is also O(n) because it uses two queues to store nodes at each level of the tree.

Conclusion

The Symmetric Tree problem on LeetCode challenges your ability to determine whether a given binary tree is symmetric or not. To solve this problem, we’ve discussed two approaches in Java: the recursive approach and the iterative approach. Both approaches provide correct solutions and have a time complexity of O(n).

Remember that the recursive approach is more intuitive and straightforward, while the iterative approach uses queues to mimic the recursive calls. You can choose either approach based on your preference and coding style.

We hope this blog post has helped you understand the Symmetric Tree problem and how to solve it in Java. Happy coding on LeetCode, and keep honing your algorithmic and programming skills!

Thank You!

Read More –

Connect Hosting Server with Domain | connect hosting with domain – https://kamleshsingad.com/how-to-connect-hosting-server-with-domain-connect-hosting/

WordPress Theme Customization | How to Install WordPress Plugins – https://kamleshsingad.com/wordpress-theme-customization-how-to-install-wordpress-plugins/

Hollow Inverted Right Triangle Star Pattern Problem | Pattern Printing in Java | Code with Kamlesh – https://kamleshsingad.com/hollow-inverted-right-triangle-star-pattern-problem-and-pattern-printing-in-java/

LEAVE A REPLY

Please enter your comment!
Please enter your name here