0100.md

100. Same Tree

Level:

Topic:

Similar Problem:

• 101. Symmetric Tree

Question

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

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

Intuition

Recursive:

• if both null, return true
• if neither null, return false
• if both val is same and traverse

Iterative:

• same as recursive but the way of traversal is iterative

Code

Time: O(n)
Space: O(n)

Recursive

public boolean 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);
}

Iterative

public boolean isSameTree(TreeNode p, TreeNode q) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(p);
    queue.add(q);

    while (!queue.isEmpty()) {
        p = queue.poll();
        q = queue.poll();
        if (p == null && q == null)
            continue;
        if (p == null || q == null)
            return false;
        if (p.val != q.val)
            return false;

        queue.add(p.left);
        queue.add(q.left);
        queue.add(p.right);
        queue.add(q.right);
    }

    return true;
}