Same Tree Problem Solution

Same Tree Problem Solution: 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 :

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

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

Output: true

Problem Solution In Python

from itertools import zip_longest

class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        for p_val, q_val in zip_longest(preorder(p), preorder(q)):
            if p_val != q_val:
                return False
        return True
    
def preorder(tree):
        yield tree and tree.val
        if tree:
            for node in preorder(tree.left):
                yield node
            for node in preorder(tree.right):
                yield node

Problem Solution In Java

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p != null && q != null && q.val == p.val) {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
        return p == null && q == null;
    }
}

Problem Solution In C++

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL)return true;
        if(p == NULL || q == NULL)return false;
        return (p->val == q->val)&&isSameTree(p->left, q->left)&&isSameTree(p->right, q->right);
    }
};

Problem Solution In C

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL) {
        return true;
    } else if ((p == NULL && q != NULL) || (p != NULL && q == NULL)) {
        return false;
    }
    if (p->val == q->val) {
        if (isSameTree(p->left , q->left) && isSameTree(p->right, q->right)) {
            return true;
        }
    }
    return false;
}

Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment