Same Tree

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        }
        
        if (p == nullptr || q == nullptr || p->val != q->val) {
            return false;
        }
        
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

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

                                            
class Solution:
    def isSameTree(self, p, q):
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if (p == NULL && q == NULL) {
        return true;
    }
    if (p == NULL || q == NULL) {
        return false;
    }
    if (p->val != q->val) {
        return false;
    }
    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 val = 0, TreeNode left = null, TreeNode right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return IsSameTree(p.left, q.left) && 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)
 * }
 */

var isSameTree = function(p, q) {
    if (!p && !q) {
        return true;
    }
    if (!p || !q || p.val !== q.val) {
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if (!p && !q) {
        return true;
    }
    if (!p || !q || p.val !== q.val) {
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   int val;
 *   TreeNode? left;
 *   TreeNode? right;
 *   TreeNode(this.val, [this.left = null, this.right = null]);
 */

class Solution {
  bool isSameTree(TreeNode? p, TreeNode? q) {
    if (p == null && q == null) {
      return true;
    }
    if (p == null || q == null) {
      return false;
    }
    if (p.val != q.val) {
      return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }
    if p.Val != q.Val {
        return false
    }
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#     end
# end

def is_same_tree(p, q)
    return true if p.nil? && q.nil?
    return false if p.nil? || q.nil?
    
    p.val == q.val && is_same_tree(p.left, q.left) && is_same_tree(p.right, q.right)
end

To solve this coding challenge, you need to verify whether two binary trees are structurally identical and have identical node values. Essentially, this means that for every corresponding node in both trees, the subtree structure and the node values must be the same. Here is a detailed explanation of how to approach solving this problem:

Explanation

Base Cases :

If both tree nodes are null (i.e., they both reach a leaf at the same time), then they are identical up to this point.
If one tree node is null and the other isn't, then the trees are not identical because a node exists in one tree but not the other.
If both nodes are not null but their values are different, then the trees are not identical because corresponding nodes must have the same value.

Recursive Check :

If the values of the current nodes in both trees are the same, you then recursively check their left children and right children.
The trees are the same if and only if their left subtrees and right subtrees are identical.

To implement this, follow these detailed steps in the pseudocode.

Detailed Steps in Pseudocode

Start with a function
isSameTree

that takes the roots of two binary trees,
p

and
q

.
If both
p

and
q

are null, return
True

because both trees are empty and thus identical.
If either
p

or
q

is null (but not both), return
False

because one tree has a node where the other does not.
If the values of the current nodes of
p

and
q

are not equal, return
False

because corresponding nodes have different values.
Recursively call
isSameTree

for the left children of
p

and
q

, and store the result.
Recursively call
isSameTree

for the right children of
p

and
q

, and store the result.
Return the logical
AND

of the results from steps 5 and 6 since both left and right subtrees must be identical.

Here is the pseudocode with comments for clarity:

                                            
# Function to determine if two trees are the same
function isSameTree(TreeNode p, TreeNode q):
    # Base case: both are null
    if p is null and q is null:
        return True
    
    # Base case: one is null, the other is not
    if p is null or q is null:
        return False
    
    # Node values differ
    if p.value != q.value:
        return False
    
    # Recursively check left subtrees
    leftSame = isSameTree(p.left, q.left)
    
    # Recursively check right subtrees
    rightSame = isSameTree(p.right, q.right)
    
    # Both left and right subtrees must be identical
    return leftSame and rightSame

By following these steps, you systematically ensure that both binary trees are traversed simultaneously. At each step, the function ensures that corresponding nodes are equivalent in terms of structure and value, thereby confirming whether the trees are identical as per the defined criteria.