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

12
September 2020

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

- 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