Grokking Tree Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Symmetric Tree
On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

Problem Statement

Given the root of a binary tree, return true if the tree is symmetric, meaning it is a mirror image of itself. Otherwise, return false.

A tree is considered symmetric if the left subtree is a mirror reflection of the right subtree.

Examples

Example 1:

  • Input: root = [1,5,5,3,4,4,3]
Image
  • Expected Output: true
  • Justification: The tree is symmetric because the left subtree mirrors the right subtree at every level.

Example 2:

  • Input: root = [1,5,5,null,3,null,3]
Image
  • Expected Output: false
  • Justification: The tree is not symmetric because the left and right subtrees do not match in structure or values.

Example 3:

  • Input: root = [1,2,2,null,3,3,null]
Image
  • Expected Output: true
  • Justification: The tree is symmetric because the left and right subtrees are mirror images in terms of structure and values.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100

Solution

To solve this problem, the goal is to check whether a binary tree is symmetric. A tree is symmetric if the left and right subtrees of the root are mirror images of each other. To achieve this, the recursive approach known as Depth First Search (DFS) is used to compare the left and right subtrees simultaneously.

The approach begins by checking whether the tree is symmetric starting from the root. A helper method, isMirror, is used to compare two nodes (starting with the root and itself). This method ensures that:

  • Both nodes are null (in which case, they are considered mirrors).
  • One node is null and the other is not (which means the tree is not symmetric).
  • Both nodes have the same value, and the left subtree of one node is compared to the right subtree of the other.

This approach ensures that every corresponding node in the left and right subtrees are compared in a mirror fashion. By checking these conditions at every step, the algorithm confirms if the tree is symmetric or not.

Step-by-Step Algorithm

  1. Call the helper method isMirror(TreeNode t1, TreeNode t2):

    • Pass the root node twice to the isMirror method to compare the left and right subtrees.
    • We begin by checking whether both t1 and t2 are null.

  2. Handle null nodes:

    • If both nodes are null, return true because two null nodes are mirrors of each other.
    • If one node is null and the other is not, return false because they are not mirrors.

  3. Compare the values of the nodes:

    • If neither node is null, compare their values (t1.val == t2.val).
    • If the values are not equal, return false because the tree is not symmetric.
    • If the values are equal, continue to the next step.

  4. Recursive comparison:

    • Check the left subtree of t1 with the right subtree of t2 by recursively calling isMirror(t1.left, t2.right).
    • Simultaneously, check the right subtree of t1 with the left subtree of t2 by recursively calling isMirror(t1.right, t2.left).

  5. Return the result:

    • Both recursive calls must return true for the current pair of nodes to be considered mirrors. If both are true, the current nodes are mirrors. Otherwise, return false.

Algorithm Walkthrough

Input: [1,5,5,3,4,4,3]

Image

  1. Initial Step:

    • The isSymmetric() method is called with the root node of the tree (value 1).

  2. First Call to isMirror():

    • The isMirror() method is called with both t1 and t2 pointing to the root node (value 1).
    • Since t1.val == t2.val (both have value 1), we move forward to check their subtrees.

  3. Check the Left and Right Subtrees:

    • Now, isMirror(t1.left, t2.right) is called to compare the left subtree of t1 and the right subtree of t2.
    • At the same time, isMirror(t1.right, t2.left) is called to compare the right subtree of t1 and the left subtree of t2.
    • Both pairs have nodes with value 5. Since 5 == 5, we move deeper into their subtrees.

  4. Second Level: Compare Subtrees:

    • Next, isMirror(t1.left.left, t2.right.right) is called to compare the left child of t1.left (value 3) with the right child of t2.right (value 3).
    • Also, isMirror(t1.left.right, t2.right.left) is called to compare the right child of t1.left (value 4) with the left child of t2.right (value 4).
    • Both comparisons return true because 3 == 3 and 4 == 4.

  5. Handle the Leaf Nodes:

    • At this point, the algorithm reaches the leaf nodes (null values).
    • The isMirror(null, null) calls check these and return true, since both sides are null.

  6. Return the Result:

    • As all recursive calls at each level have returned true, the algorithm concludes that the tree is symmetric.
    • The isSymmetric() method returns true, confirming that the tree [1,5,5,3,4,4,3] is indeed symmetric.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

The isMirror method recursively checks every node in the tree to determine whether the tree is symmetric. Each node is visited once, meaning that for n nodes, the algorithm runs in O(n) time.

Space Complexity

The space complexity is determined by the recursion stack. In the worst case (a skewed tree), the depth of the recursion could be n, leading to a space complexity of O(n). However, for a balanced tree, the recursion depth would be O(log n).

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity