The blog for Design Patterns, Linux, HA and Myself!

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

- All Elements in Two Binary Search Trees Solution
- Construct Binary Search Tree From Preorder Traversal Solution
- Maximum Binary Tree Solution
- Sum of Nodes With Even Valued Grandparent Solution
- Deepest Leaves Sum Solution
- Symmetric Tree or Mirror Tree Solution
- Diameter of Binary Tree Solution
- Binary Tree Paths Solution
- Cousins in Binary Tree Solution
- Sum of Left Leaves Solution
- Same Tree or Equal Tree Solution
- Minimum Absolute Difference in BST Solution
- Construct String From Binary Tree Solution - Leetcode
- Two Sum IV - Input is a BST Solution - Leetcode
- Convert BST to Greater Tree Solution - Leetcode
- Convert Sorted Array to Binary Search Tree Solution
- Average of Levels in Binary Tree Solution
- Leaf Similar Trees Solution - Leetcode
- Sum of Root to Leaf Binary Numbers - Leetcode
- Univalued Binary Tree - Leetcode
- Maximum Depth of N Ary Tree - Leetcode
- Increasing Order Search Tree - Leetcode
- Merge Two Binary Trees Solution
- Range Sum of BST - Leetcode