Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Symmetric Tree | Leetcode 101 | Recursive DFS Approach
    Data Structures & Algorithms

    Symmetric Tree | Leetcode 101 | Recursive DFS Approach

    codeanddebugBy codeanddebug2 September 2025No Comments3 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of a question to solve Symmetric Tree
    Share
    Facebook Twitter LinkedIn Pinterest Email

    The Symmetric Tree problem asks us to check whether a given binary tree is a mirror image of itself around its center.

    In simple terms:

    • A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree.
    • For every node, the left child of one subtree must match the right child of the other subtree, and vice versa.

    Here’s the [Problem Link] to begin with.


    Examples

    Example 1

    Input: [1,2,2,3,4,4,3]
    
            1
           / \
          2   2
         / \ / \
        3  4 4  3
    
    Output: True
    Explanation: The tree is symmetric.

    Example 2

    Input: [1,2,2,null,3,null,3]
    
            1
           / \
          2   2
           \   \
            3   3
    
    Output: False
    Explanation: The tree is not symmetric.

    Intuition

    To determine whether a tree is symmetric:

    • Compare the left subtree and the right subtree.
    • At every step:
      • If both nodes are None → symmetric so far.
      • If only one is None → not symmetric.
      • If values differ → not symmetric.
      • Otherwise, recursively check:
        • Left child of node1 with Right child of node2.
        • Right child of node1 with Left child of node2.

    This recursive mirroring ensures symmetry validation.


    Solution: Recursive DFS

    Code Implementation

    class Solution:
        def solve(self, node1, node2):
            if node1 is None or node2 is None:
                return node1 == node2
            if node1.val != node2.val:
                return False
    
            # Compare left of one with right of the other
            leftSide = self.solve(node1.left, node2.right)
            if leftSide == False:
                return False
    
            # Compare right of one with left of the other
            rightSide = self.solve(node1.right, node2.left)
            if rightSide == False:
                return False
    
            return leftSide and rightSide
    
        def isSymmetric(self, root: Optional[TreeNode]) -> bool:
            return self.solve(root.left, root.right)

    Code Explanation

    • solve(node1, node2):
      • Compares two nodes recursively.
      • Handles base cases where nodes are None.
      • Checks value equality.
      • Recursively compares opposite children:
        • node1.left with node2.right.
        • node1.right with node2.left.
    • isSymmetric(root):
      • Starts the recursion by comparing the left and right children of the root.

    Dry Run

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

    1. Start: solve(root.left=2, root.right=2) → values match.
    2. Compare: solve(2.left=3, 2.right=3) → values match.
    3. Compare: solve(3.left=None, 3.right=None) → symmetric.
    4. Compare: solve(2.right=4, 2.left=4) → values match.
    5. Continue until all recursive checks succeed.

    Final Result = True.


    Time and Space Complexity

    • Time Complexity: O(N)
      • Each node is visited once.
    • Space Complexity: O(H)
      • Due to recursion stack, where H = height of the tree.
      • In worst case (skewed tree), space = O(N).
      • In balanced tree, space = O(log N).

    Conclusion

    The Symmetric Tree problem can be solved efficiently using recursive DFS.

    • At every step, we compare the left subtree of one side with the right subtree of the other.
    • If all corresponding nodes match, the tree is symmetric.

    This approach is clean, recursive, and efficient, running in O(N) time with O(H) space.


    Join our Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Binary Trees Easy
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleBinary Tree Right Side View | Leetcode 199 | BFS and DFS Approaches
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Binary Tree Right Side View | Leetcode 199 | BFS and DFS Approaches

    2 September 2025
    Data Structures & Algorithms

    Bottom View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025
    Data Structures & Algorithms

    Top View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (240)
      • Beginner (82)
      • Expert (52)
      • Intermediate (106)
    • Uncategorised (1)
    Recent Posts

    Symmetric Tree | Leetcode 101 | Recursive DFS Approach

    2 September 2025

    Binary Tree Right Side View | Leetcode 199 | BFS and DFS Approaches

    2 September 2025

    Bottom View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025

    Top View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025

    Vertical Order Traversal of a Binary Tree | Leetcode 987 | BFS + Sorting Solution

    2 September 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.