Same Tree

Check if two binary trees are identical. Identical means the two binary trees have the same structure and every identical position has the same value.

Question

Check if two binary trees are identical. Identical means the two binary trees have the same structure and every identical position has the same value.

Example:

Input:{1,2,2,4},{1,2,2,4}
Output:true
Explanation:
        1                   1
       / \                 / \
      2   2   and         2   2
     /                   /
    4                   4

are identical.


Input:{1,2,3,4},{1,2,3,#,4}
Output:false
Explanation:

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

are not identical.

Analyzation

Recursion

Just two steps:

Check if the trees exists, if not, return True.

If they both exists and the current nodes are identical, then return to see whether their corresponding left subtree and right subtree are identical. If so, return True.

The Code

class Solution:
    """
    @param a: the root of binary tree a.
    @param b: the root of binary tree b.
    @return: true if they are identical, or false.
    """
    def isIdentical(self, a, b):
        # write your code here
        if a is None and b is None:
            return True
            
        if a and b and a.val == b.val:
            return self.isIdentical(a.left, b.left) and self.isIdentical(a.right, b.right)
        
        return False

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).