Symmetric Tree Problem on LeetCode in Python

Spread the love

Introduction

Binary trees are widely used in various fields, including computer networks, databases, and graphics. One of the intriguing properties of a binary tree is its symmetry. The Symmetric Tree problem on LeetCode deals with this property. In this article, we will take an in-depth look at the Symmetric Tree problem and explore various approaches to solve it using Python.

Table of Contents

  1. Introduction
  2. Understanding the Problem Statement
  3. Recursive Approach
  4. Iterative Approach Using a Queue
  5. Time and Space Complexity Analysis
  6. Practical Applications
  7. Conclusion

Understanding the Problem Statement

The “Symmetric Tree” problem on LeetCode is defined as follows:

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

Example:

Input: root = [1,2,2,3,4,4,3]
Output: true
Input: root = [1,2,2,null,3,null,3]
Output: false

In simpler terms, we have to check whether the given binary tree is a mirror image of itself.

Recursive Approach

The most intuitive approach for checking the symmetry is a recursive one. For a tree to be symmetric, the left subtree of the root must be a mirror image of its right subtree.

We can create a recursive function, is_mirror, that takes two nodes and compares them. The base case would be that if both nodes are None, it’s a mirror. If only one of them is None, or they have different values, it’s not a mirror. Finally, the recursive case would be that a tree is a mirror if the left subtree of the first node is a mirror of the right subtree of the second node and vice versa.

Here’s what the Python code looks like:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def is_mirror(node1, node2):
            if not node1 and not node2:
                return True
            if not node1 or not node2:
                return False
            
            return (node1.val == node2.val) and is_mirror(node1.left, node2.right) and is_mirror(node1.right, node2.left)
        
        return is_mirror(root, root)

Iterative Approach Using a Queue

Using recursion can lead to a deep call stack for very deep trees. An alternative is an iterative approach that uses a queue. Similar to the recursive approach, we compare pairs of nodes for their symmetry. We enqueue nodes in pairs and then dequeue and compare them. We also enqueue the children of these nodes in the queue in the correct order to check for symmetry.

Here’s the Python code for this approach:

from collections import deque

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # Initialize a queue and enqueue the root twice
        queue = deque([root, root])
        
        # Continue until the queue is empty
        while queue:
            node1 = queue.popleft()
            node2 = queue.popleft()
            
            # If both nodes are None, continue to next iteration
            if not node1 and not node2:
                continue
            
            # If only one of the nodes is None, or the values are different, return False
            if not node1 or not node2 or node1.val != node2.val:
                return False
            
            # Enqueue the children in the correct order
            queue.append(node1.left)
            queue.append(node2.right)
            queue.append(node1.right)
            queue.append(node2.left)
        
        return True

Time and Space Complexity Analysis

  1. Recursive Approach: The time complexity is O(n), where n is the number of nodes in the tree as each node is visited once. The space complexity is O(h), where h is the height of the tree due to the function call stack in recursion.
  2. Iterative Approach Using a Queue: The time complexity is O(n) as each node is enqueued and dequeued once. The space complexity is O(w), where w is the maximum width of the tree, accounting for the queue storage.

Practical Applications

Symmetry in binary trees is an important concept that can be used in various fields. For instance:

  1. Computer Graphics: Symmetric trees can be used to model symmetric structures and patterns in computer graphics.
  2. Data Analysis: In decision tree analysis, checking for symmetry might help in pruning and optimizing the decision tree.
  3. Network Topology: Symmetric binary trees can represent symmetrical network topologies, which have redundancy and reliability advantages.

Conclusion

In this article, we explored the Symmetric Tree problem on LeetCode. We discussed two main approaches to solving this problem in Python – a recursive approach and an iterative approach using a queue. Understanding these approaches not only helps in solving this particular problem but also forms a basis for dealing with more complex tree-based problems. Furthermore, recognizing the symmetry property of binary trees can be advantageous in various real-world applications.

Leave a Reply