101. Symmetric Tree

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Problem Description

The problem provided is about checking symmetry in a binary tree. Specifically, you are given a binary tree's root node, and your task is to determine if the tree is a mirror image of itself when divided down the middle. Essentially, this is asking whether the left and right sub-trees of the tree are mirror images of each other.

Flowchart Walkthrough

Let's use the provided algorithm flowchart to deduce the appropriate search pattern for solving LeetCode 101: Symmetric Tree. You can view and follow along using the Flowchart. Here are the steps based on the flowchart:

Is it a graph?
- Yes: A tree is a specific type of graph.
Is it a tree?
- Yes: The problem explicitly deals with a tree data structure.
DFS
- As the problem is directly concerned with a tree and checking symmetry involves exploring all nodes to compare mirror images (left versus right at each subtree), Depth-First Search (DFS) is suitable.

Thus, the flowchart leads to utilizing Depth-First Search (DFS) as the appropriate method for a tree structure when checking for symmetrical properties, as we traverse down the tree in branches comparing corresponding nodes for symmetry.

Intuition

To solve this problem, the idea is to use a Depth-First Search (DFS) approach. The solution involves recursively comparing the left sub-tree with the right sub-tree to ensure they are mirrors of each other. This is done by checking that:

The value of the current node in the left sub-tree is equal to the value of the current node in the right sub-tree.
The left child of the left sub-tree is a mirror of the right child of the right sub-tree.
The right child of the left sub-tree is a mirror of the left child of the right sub-tree.

We can start this process by comparing the root node with itself, initiating symmetry checks between its left and right child nodes. If both nodes are null, it means we are comparing leaves, and thus they are symmetric. If only one is null or the values of the two nodes are not equal, then the tree is not symmetric.

The recursion continues this process of mirroring the checks to progressively lower levels of the tree until all mirrored nodes pass the comparisons, or a pair of nodes fails, which indicates the tree is not symmetric.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution to the given problem relies on a Depth-First Search (DFS) algorithm, which explores as far as possible along each branch before backtracking. Here, DFS is applied recursively through a helper function named dfs.

The dfs function is designed to take two nodes as arguments—root1 and root2. Initially, these arguments are both set to the root of the whole tree since we start by comparing the tree to itself. Here's how the dfs function works:

Base case for null nodes: If both root1 and root2 are None, this means that both branches being compared have reached the end simultaneously, indicating a mirrored structure at this branch level. So, it returns True.
Case for asymmetry: If one of the nodes is None (while the other isn’t), or if the values of the two nodes are not equal, the function identifies a break in symmetry and returns False.
Recursive calls: If neither of the above cases is true, the dfs function calls itself twice more: once comparing the left child of root1 with the right child of root2, and then comparing the right child of root1 with the left child of root2. This is the crux of the mirroring check, making sure that each "mirror" position across the two sub-trees holds an equivalent value.

The dfs function uses a logical AND && to combine the results of its recursive calls. Both calls must return True for the function to return True, ensuring that all parts of the tree adhere to the symmetry condition.

Finally, the isSymmetric function of the Solution class makes the initial call to dfs using the root as both arguments. If the entire tree is symmetric, the function will eventually return True; if any asymmetry is found at any level, it will return False.

The overall time complexity of the algorithm is O(n), where n is the number of nodes in the tree, because each node is visited once. The space complexity is also O(n) for the call stack due to recursion, which in the worst case, could be the height of the tree. For a balanced tree, this would result in a space complexity of O(log n) due to its height.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple, symmetric binary tree to illustrate the solution approach. Here is the tree structure:

Now let's walk through the dfs function with this tree to see how it validates symmetry:

The isSymmetric function starts and calls dfs, passing the root node as both root1 and root2, since we're comparing the tree with itself.
As none of the root1 and root2 are null and their values are equal (value 1), the dfs function continues to the recursive calls.
Two dfs calls are made: one for root1's left (Node 2) and root2's right (also Node 2), the other for root1's right (Node 2) and root2's left (also Node 2). Both pairs are identical, so we proceed.
Now, from the first recursive call of dfs, two more recursive calls are made:
- Compare root1's left (Node 3) and root2's right (Node 3).
- Compare root1's right (Node 4) and root2's left (Node 4).
Simultaneously, from the second recursive call of dfs, another two recursive calls are made:
- Compare root1's left (Node 4) and root2's right (Node 4).
- Compare root1's right (Node 3) and root2's left (Node 3).
All subsequent recursive calls find that the nodes are either simultaneously null or with equal values, satisfying the base case and the equality check condition. Hence, every recursive call returns True.
Since the && operator is used to combine the results, and all recursive calls returned True, the initial call to dfs also returns True.
The isSymmetric function concludes that the tree is symmetric.

This tree has passed all the checks outlined in the approach; each node on the left has a corresponding node with equal value on the right, and vice versa. The recursion accurately captures this mirror image property, ensuring that a node and its "mirror" node are consistently equal in value.

Solution Implementation

1class TreeNode:
2    # Definition for a binary tree node.
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def isSymmetric(self, root: TreeNode) -> bool:
10        """
11        Check if a binary tree is symmetric around its center.
12        A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree.
13      
14        :param root: TreeNode
15        :return: bool, true if the tree is symmetric, false otherwise
16        """
17
18        def is_mirror(node1: TreeNode, node2: TreeNode) -> bool:
19            """
20            Helper function that checks if two trees are mirror images of each other.
21          
22            :param node1: TreeNode, root of the first tree or subtree
23            :param node2: TreeNode, root of the second tree or subtree
24            :return: bool, true if both trees are mirror images, false otherwise
25            """
26            # Both nodes are None, meaning both subtrees are empty, thus symmetric
27            if node1 is None and node2 is None:
28                return True
29            # If only one of the nodes is None or if the values don't match, the subtrees aren't mirrors
30            if node1 is None or node2 is None or node1.val != node2.val:
31                return False
32            # Check the outer and inner pairs of subtrees
33            return is_mirror(node1.left, node2.right) and is_mirror(node1.right, node2.left)
34
35        # Start the recursion with root as both parameters, as the check is for the tree with itself
36        return is_mirror(root, root)
37

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;        // The value of the node
6    TreeNode left;  // Pointer to the left child
7    TreeNode right; // Pointer to the right child
8
9    // Constructors for creating a tree node
10    TreeNode() {}
11    TreeNode(int value) { this.val = value; }
12    TreeNode(int value, TreeNode leftChild, TreeNode rightChild) {
13        this.val = value;
14        this.left = leftChild;
15        this.right = rightChild;
16    }
17}
18
19class Solution {
20    /**
21     * Determines if a binary tree is symmetric around its center (mirrored).
22     * 
23     * @param root The root of the tree.
24     * @return true if the tree is symmetric, false otherwise.
25     */
26    public boolean isSymmetric(TreeNode root) {
27        // Start DFS from the root for both subtrees for comparison.
28        return isMirror(root, root);
29    }
30
31    /**
32     * Helper method to perform a DFS to check for symmetry by comparing nodes.
33     *
34     * @param node1 The current node from the first subtree.
35     * @param node2 The current node from the second subtree.
36     * @return true if the two subtrees are mirrors of each other, false otherwise.
37     */
38    private boolean isMirror(TreeNode node1, TreeNode node2) {
39        // Both nodes are null, meaning this branch is symmetric.
40        if (node1 == null && node2 == null) {
41            return true;
42        }
43        // If only one of the nodes is null, or their values differ,
44        // the tree cannot be symmetric.
45        if (node1 == null || node2 == null || node1.val != node2.val) {
46            return false;
47        }
48        // Continue to compare the left subtree of node1 with the right subtree of node2
49        // and the right subtree of node1 with the left subtree of node2. Both comparisons
50        // must be true for the subtree to be symmetric.
51        return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
52    }
53}
54

1// Definition for a binary tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6    TreeNode() : val(0), left(nullptr), right(nullptr) {}
7    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
9};
10
11class Solution {
12public:
13    // Function to check whether a binary tree is symmetric around its center
14    bool isSymmetric(TreeNode* root) {
15        // Define a lambda function to recursively check the symmetry
16        function<bool(TreeNode*, TreeNode*)> checkSymmetry = [&](TreeNode* leftSubtree, TreeNode* rightSubtree) -> bool {
17            // If both subtrees are null, they are symmetric
18            if (!leftSubtree && !rightSubtree) return true;
19          
20            // If one subtree is null or the values are different, they are not symmetric
21            if (!leftSubtree || !rightSubtree || leftSubtree->val != rightSubtree->val) return false;
22          
23            // Recursively check the symmetry of subtrees 
24            // The left subtree of the left node and the right subtree of the right node
25            // The right subtree of the left node and the left subtree of the right node
26            return checkSymmetry(leftSubtree->left, rightSubtree->right) && 
27                   checkSymmetry(leftSubtree->right, rightSubtree->left);
28        };
29      
30        // Initialize the recursive function with the root of the tree
31        return checkSymmetry(root, root);
32    }
33};
34

1// TreeNode definition for a binary tree node.
2class TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6
7  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8    this.val = val === undefined ? 0 : val;
9    this.left = left === undefined ? null : left;
10    this.right = right === undefined ? null : right;
11  }
12}
13
14/**
15 * A function that performs a depth-first search to check if two
16 * subtrees are mirrors of each other. 
17 * 
18 * @param subtreeOne The root node of the first subtree.
19 * @param subtreeTwo The root node of the second subtree.
20 * @returns A boolean indicating whether the subtrees are symmetric.
21 */
22const depthFirstSearch = (subtreeOne: TreeNode | null, subtreeTwo: TreeNode | null): boolean => {
23  // If both subtrees are null, they are symmetric (base case).
24  if (subtreeOne == null && subtreeTwo == null) {
25    return true;
26  }
27  // If one is null and the other is not, or if the values are different, they are not symmetric.
28  if (subtreeOne == null || subtreeTwo == null || subtreeOne.val != subtreeTwo.val) {
29    return false;
30  }
31  // Recursively compare the left subtree of the first subtree with the right subtree of the second subtree
32  // and the right subtree of the first subtree with the left subtree of the second subtree.
33  return depthFirstSearch(subtreeOne.left, subtreeTwo.right) && depthFirstSearch(subtreeOne.right, subtreeTwo.left);
34};
35
36/**
37 * Given the root of a binary tree, determine if it is a mirror of itself
38 * (i.e., symmetric around its center).
39 * 
40 * @param root The root node of the binary tree.
41 * @returns A boolean indicating whether the binary tree is symmetric.
42 */
43function isSymmetric(root: TreeNode | null): boolean {
44  // Handle the edge case where the tree is empty.
45  if (root == null) {
46    return true;
47  }
48  // Use helper function to compare the left and right subtree of the root.
49  return depthFirstSearch(root.left, root.right);
50}
51

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(n), where n is the number of nodes in the binary tree. This is because the recursive function dfs visits every node exactly once in the case of a perfectly symmetrical tree, checking symmetry for the left and the right subtree.

Space Complexity

The space complexity of the code is primarily determined by the recursion stack used in the dfs function. In the worst-case scenario (a completely balanced tree), the height of the tree will be log(n) (since every level of the tree is fully filled), resulting in a space complexity of O(log(n)).

However, in the worst-case scenario of an unbalanced tree (such as a degenerate tree where every node only has one child), the space complexity would be O(n) because the call stack would grow linearly with the number of nodes, as the tree would effectively become a linked list.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know