Same Tree or Equal Tree Solution

Leetcode Solution: Understand and solve Leetcode problem Same Tree(100)

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

Same Tree or Equal Tree Solution

Leetcode Solution: Understand and solve Leetcode problem Same Tree(100)

Related Pages: