Codiwan.com

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

In this article we’ll be solving the problem: Same Tree. Just like the problem, Convert BST to Greater Tree and Merge Two Binary Trees, this problem also requires a slight modification in a simple Tree Traversal approach.

```		```

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have
the same value.

Example 1:

Input:     1         1
/ \       / \
2   3     2   3

[1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
/           \
2             2

[1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
/ \       / \
2   1     1   2

[1,2,1],   [1,1,2]

Output: false

```
```

To solve this problem, we’ll be traversing the input tree with Pre Order Tree Traversal approach.

• We’ll traverse both the trees together
• If we encounter a node in both the trees then we’ll compare their values and return false if they are unequal.
• If the values are equal then we continue the traversal using the Pre Order Tree Traversal approach
• If we encounter a node in one tree and NULL in another tree then we stop the traversal and return false
• If we encounter NULL in both the cases then we return true.

Here is the program for that:

``````func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q != nil {
return false
}
if p != nil && q == nil {
return false
}
if p == nil && q == nil {
return true
}
if p.Val != q.Val {
return false
}
isEqual := isSameTree(p.Left, q.Left)
if !isEqual {
return false
}
return isSameTree(p.Right, q.Right)
}
``````

This program is available on GitHub as well. Here we’re using the Pre Order tree traversal approach. We return `false` if the values are not same and stop the traversal at that instance.

Loading Comments... 