Symmetric Tree or Mirror Tree Solution

Leetcode Solution: Understand and solve Leetcode problem Symmetric Tree or Mirror Tree (101)

13 September 2020

In this article we’ll be solving the problem: Symmetric Tree. Just like the problem, Diameter of Binary Tree and Merge Two Binary Trees, this problem also requires a some modification in a simple Tree Traversal approach.

		
				
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

But the following [1,2,2,null,3,null,3] is not:

        1
       / \
      2   2
       \   \
       3    3

This problem is one of the most common problems that you’re going to find in the Tree Traversal category. The solution to this problem is very simple and requires a small change in the Pre Order Tree traversal approach.

We’ll have to perform a pre order tree traversal on the left and right children of a node simultaneously and compare their values. If their values do not match then we’ll stop the traversal there otherwise we’ll compare the left and right children of one left node with the right and left children of the other node. Here’s an example tree traversal of a symmetric tree:


type TreeNode struct {
  Val int
  Left *TreeNode
  Right *TreeNode
}

func isSymmetric(root *TreeNode) bool {
    return preOrder(root, root)
}

func preOrder(node1 *TreeNode, node2 *TreeNode) bool {
    if node1 == nil && node2 != nil {
        return false
    }
    if node1 != nil && node2 == nil {
        return false
    }
    if node1 == nil && node2 ==nil {
        return true
    }
    if node1.Val != node2.Val {
        return false
    }
    isEqual := preOrder(node1.Left, node2.Right)
    if !isEqual {
        return false
    }
    return preOrder(node1.Right, node2.Left)
}

This program is available on GitHub as well. Here we’re using the Pre Order tree traversal approach. We compare the node1 and node2 value then recursively call the preOrder function with left child of node1 with the right child of node2 and vice versa.

Loading Comments... Disqus Loader

Symmetric Tree or Mirror Tree Solution

Leetcode Solution: Understand and solve Leetcode problem Symmetric Tree or Mirror Tree (101)

Related Pages: