Same Tree

Easy Problem 65 of 151 Java and Python

Problem

Given the roots of two binary trees p and q, return true if they are the same: structurally identical, with equal values in matching nodes.

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
Why: Same values, different shape.

Constraints

0 ≤ number of nodes in each tree ≤ 100

Explanation

Two trees are the same when their roots match and their left subtrees are the same and their right subtrees are the same. Two empty trees are the same; one empty and one not are different.

Approach 1 · Naive

Serialize both and compare

Time O(n + m)
Space O(n + m)

Write each tree as a string that includes null markers (so shape is captured), and compare the strings.

Preorder-serialize each tree, writing "#" for null.
Return whether the strings are equal.

Java

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return serialize(p).equals(serialize(q));
    }

    private String serialize(TreeNode node) {
        if (node == null) {
            return "#";
        }
        return node.val + "," + serialize(node.left) + "," + serialize(node.right);
    }
}

Python

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def serialize(node):
            if not node:
                return "#"
            return f"{node.val},{serialize(node.left)},{serialize(node.right)}"

        return serialize(p) == serialize(q)

Approach 2 · Optimal

Recursive comparison

Time O(min(n, m))
Space O(h)

Compare the two roots, then both pairs of subtrees, stopping at the first difference.

If both are null, return true; if one is null, return false.
Return p.val == q.val && same(p.left, q.left) && same(p.right, q.right).

Java

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

Python

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p or not q:
            return p is q
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Complexity compared

Approach	Time	Space
Naive Serialize both and compare	O(n + m)	O(n + m)
Optimal Recursive comparison	O(min(n, m))	O(h)

Key takeaways

Serializations must include null markers; otherwise [1, 2] and [1, null, 2] look the same.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem