Solution For Same Tree

The Same Tree problem on LeetCode asks you to compare two binary trees and determine if they are identical. In other words, the two trees have the same structure and the same node values.

One way to approach this problem is to use a recursive algorithm. We can start by defining a helper function that takes two tree nodes as arguments and returns a boolean value indicating whether or not the two trees are identical.

Here’s the code for the helper function:

“`
bool isSameTree(TreeNode p, TreeNode q) {
// If both nodes are null, they are equal
if (!p && !q) {
return true;
}

// If only one node is null, they are not equal
if (!p || !q) {
    return false;
}

// If the node values are not equal, they are not equal
if (p->val != q->val) {
    return false;
}

// Recursively compare the left and right subtrees
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

}
“`

The helper function takes two tree nodes as arguments, which represent the roots of the two trees we want to compare. We start by checking if both nodes are null. If they are, we return true, since two null nodes are considered equal.

If only one node is null, we return false, since a null node cannot be equal to a non-null node.

If the node values are not equal, we return false as well, since the two nodes are not identical.

Finally, if all the above conditions are false, we recursively compare the left and right subtrees of the two nodes by calling the helper function on each pair of corresponding left and right child nodes. If the left and right subtrees of the two nodes are also identical, the function returns true. Otherwise, it returns false.

To solve the Same Tree problem on LeetCode, we can simply call the isSameTree function on the two given tree nodes, which represent the roots of the two trees we want to compare. If the function returns true, the two trees are identical. Otherwise, they are not.

Here’s the complete code for the Same Tree problem:

“`
/
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
/
class Solution {
public:
bool isSameTree(TreeNode p, TreeNode* q) {
// If both nodes are null, they are equal
if (!p && !q) {
return true;
}

    // If only one node is null, they are not equal
    if (!p || !q) {
        return false;
    }

    // If the node values are not equal, they are not equal
    if (p->val != q->val) {
        return false;
    }

    // Recursively compare the left and right subtrees
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

};
“`

Step by Step Implementation For Same Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // p and q are both null
        if (p == null && q == null) return true;
        // one of p and q is null
        if (q == null || p == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.right, q.right) &&
               isSameTree(p.left, q.left);
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        #if both trees are empty, return true
        if not p and not q:
            return True
        #if one tree is empty, the other is not, return false
        if not p or not q:
            return False
        #if values of the root nodes are not equal, return false
        if p.val != q.val:
            return False
        #return whether the left subtrees and right subtrees are equal
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    // if both trees are null, return true
    if (!p && !q) {
        return true;
    }
    // if one tree is null and the other is not, return false
    if (!p || !q) {
        return false;
    }
    // if the values of the nodes are not equal, return false
    if (p.val !== q.val) {
        return false;
    }
    // recursively call isSameTree on the left and right subtrees
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // if both are null, return true
        if (!p && !q) return true;
        // if one is null and the other isn't, return false
        if (!p || !q) return false;
        // if the values are different, return false
        if (p->val != q->val) return false;
        // return whether the left and right subtrees are the same
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        //if both trees are null, they are the same
        if(p == null && q == null){
            return true;
        }
        //if one tree is null and the other isn't, they are not the same
        else if(p == null || q == null){
            return false;
        }
        //if the values of the nodes are not the same, the trees are not the same
        else if(p.val != q.val){
            return false;
        }
        //compare the left subtrees and the right subtrees
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
    }
}