101. Symmetric Tree

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree
Leetcode Link

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.

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:

  1. 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.
  2. The left child of the left sub-tree is a mirror of the right child of the right sub-tree.
  3. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

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:

  1. 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.

  2. 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.

  3. 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.

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

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

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

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

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

  1. The isSymmetric function starts and calls dfs, passing the root node as both root1 and root2, since we're comparing the tree with itself.

  2. As none of the root1 and root2 are null and their values are equal (value 1), the dfs function continues to the recursive calls.

  3. 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.

  4. 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).

  5. 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).

  6. 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.

  7. Since the && operator is used to combine the results, and all recursive calls returned True, the initial call to dfs also returns True.

  8. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which data structure is used to implement priority queue?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ