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
- Understanding the Problem Statement
- Recursive Approach
- Iterative Approach Using a Queue
- Time and Space Complexity Analysis
- Practical Applications
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).
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.
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
- 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.
- 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.
Symmetry in binary trees is an important concept that can be used in various fields. For instance:
- Computer Graphics: Symmetric trees can be used to model symmetric structures and patterns in computer graphics.
- Data Analysis: In decision tree analysis, checking for symmetry might help in pruning and optimizing the decision tree.
- Network Topology: Symmetric binary trees can represent symmetrical network topologies, which have redundancy and reliability advantages.
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.