100. Same Tree

Easy

Problem Description

Given the roots of two binary trees p and q, 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.

Examples

Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


# 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
def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    # If both nodes are None, trees are identical
    if not p and not q:
        return True
    
    # If one node is None and other isn't, trees are different
    if not p or not q:
        return False
    
    # Check current nodes and recursively check subtrees
    return (p.val == q.val and 
            isSameTree(p.left, q.left) and 
            isSameTree(p.right, q.right))

Java Solution


/**
 * 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) {
        // If both nodes are null, trees are identical
        if (p == null && q == null) {
            return true;
        }
        
        // If one node is null and other isn't, trees are different
        if (p == null || q == null) {
            return false;
        }
        
        // Check current nodes and recursively check subtrees
        return p.val == q.val && 
               isSameTree(p.left, q.left) && 
               isSameTree(p.right, q.right);
    }
}

C++ Solution


/**
 * 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 nodes are null, trees are identical
        if (!p && !q) {
            return true;
        }
        
        // If one node is null and other isn't, trees are different
        if (!p || !q) {
            return false;
        }
        
        // Check current nodes and recursively check subtrees
        return p->val == q->val && 
               isSameTree(p->left, q->left) && 
               isSameTree(p->right, q->right);
    }
};

JavaScript Solution


/**
 * 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 nodes are null, trees are identical
    if (!p && !q) {
        return true;
    }
    
    // If one node is null and other isn't, trees are different
    if (!p || !q) {
        return false;
    }
    
    // Check current nodes and recursively check subtrees
    return p.val === q.val && 
           isSameTree(p.left, q.left) && 
           isSameTree(p.right, q.right);
};

C# Solution


/**
 * 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 both nodes are null, trees are identical
        if (p == null && q == null) {
            return true;
        }
        
        // If one node is null and other isn't, trees are different
        if (p == null || q == null) {
            return false;
        }
        
        // Check current nodes and recursively check subtrees
        return p.val == q.val && 
               IsSameTree(p.left, q.left) && 
               IsSameTree(p.right, q.right);
    }
}

Complexity Analysis

Solution Explanation

This solution uses recursive comparison of tree nodes:

Key points: