Same Tree (LC 100): Recursive and Iterative Comparison

Decide whether two binary trees are identical in both shape and node values. Compare the roots, then the left and right subtrees, recursively or with a queue of node pairs. O(n) time, O(h) space for the recursion.

Language Selection

Choose your preferred programming language

Showing: Python

Same Tree

Problem Statement

You are given the roots p and q of two binary trees. Return true if the two trees are identical and false otherwise.

Two trees are identical when they have exactly the same shape and every pair of nodes in matching positions holds the same value. Two empty trees are identical. A tree is never identical to a tree that has an extra or missing child anywhere, even if the values read the same in some traversal order.

Examples

Example 1:

Input: p = [5,3,8], q = [5,3,8]
Output: true
Explanation: Both trees have root 5, left child 3 and right child 8.

Example 2:

Input: p = [4,7], q = [4,null,7]
Output: false
Explanation: In p the 7 is the left child of 4; in q it is the right child.
The values match but the shapes do not.

Example 3:

Input: p = [2,6,9], q = [2,9,6]
Output: false
Explanation: The shapes match, but the left children differ (6 versus 9).

Constraints

  • Each tree has between 0 and 100 nodes.
  • -10^4 <= Node.val <= 10^4

Approach 1: Recursive DFS

Algorithm

The definition of “identical” is itself recursive: two trees are the same when their roots match and their left subtrees are the same and their right subtrees are the same. The code follows that sentence directly.

  1. If both nodes are null, return true (two empty trees match).
  2. If exactly one is null, return false (one tree has a node the other lacks).
  3. If the values differ, return false.
  4. Otherwise return isSameTree(p.left, q.left) && isSameTree(p.right, q.right).

The && short-circuits, so the first mismatch stops the search.

Implementation

Python:

# 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
from typing import Optional


class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # Both empty: identical
        if p is None and q is None:
            return True
        # Exactly one empty, or different values: not identical
        if p is None or q is None or p.val != q.val:
            return False
        # Roots match; both subtree pairs must match too
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Java:

/**
 * 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) {
        // Both empty: identical
        if (p == null && q == null) {
            return true;
        }
        // Exactly one empty, or different values: not identical
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        // Roots match; both subtree pairs must match too
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Go:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    // Both empty: identical
    if p == nil && q == nil {
        return true
    }
    // Exactly one empty, or different values: not identical
    if p == nil || q == nil || p.Val != q.Val {
        return false
    }
    // Roots match; both subtree pairs must match too
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

JavaScript:

/**
 * 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) {
    // Both empty: identical
    if (p === null && q === null) {
        return true;
    }
    // Exactly one empty, or different values: not identical
    if (p === null || q === null || p.val !== q.val) {
        return false;
    }
    // Roots match; both subtree pairs must match too
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

C#:

/**
 * 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) {
        // Both empty: identical
        if (p == null && q == null) {
            return true;
        }
        // Exactly one empty, or different values: not identical
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        // Roots match; both subtree pairs must match too
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
    }
}

C++:

/**
 * 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) {
        // Both empty: identical
        if (p == nullptr && q == nullptr) {
            return true;
        }
        // Exactly one empty, or different values: not identical
        if (p == nullptr || q == nullptr || p->val != q->val) {
            return false;
        }
        // Roots match; both subtree pairs must match too
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

Complexity Analysis

  • Time: O(n), where n is the number of nodes in the smaller tree. Each matching pair of positions is visited at most once, and the walk stops at the first difference, so it never goes deeper than the smaller tree.
  • Space: O(h) for the recursion stack, where h is the height of the smaller tree: O(log n) for a balanced tree and O(n) for a chain. With at most 100 nodes, the depth is at most 100.

Approach 2: Iterative BFS with a Queue of Pairs

Algorithm

The same check works without recursion. Keep a queue of node pairs that still need comparing, starting with (p, q). Each pair is checked with the same three rules; when the two nodes match, their left children and their right children are queued as two new pairs.

  1. Put the pair (p, q) in a queue.
  2. While the queue is not empty, take out a pair (a, b):
    • If both are null, continue with the next pair.
    • If exactly one is null, or a.val != b.val, return false.
    • Otherwise queue (a.left, b.left) and (a.right, b.right).
  3. If the queue empties without a mismatch, return true.

A stack instead of a queue works just as well; only the visiting order changes.

Implementation

Python:

# 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
from collections import deque
from typing import Optional


class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        queue = deque([(p, q)])
        while queue:
            a, b = queue.popleft()
            # Two empty positions match; move on
            if a is None and b is None:
                continue
            # Missing node on one side, or different values
            if a is None or b is None or a.val != b.val:
                return False
            # Compare the children position by position later
            queue.append((a.left, b.left))
            queue.append((a.right, b.right))
        return True

Java:

/**
 * 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;
 *     }
 * }
 */
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // ArrayDeque rejects nulls, so store each pair as a two-element array
        Deque<TreeNode[]> queue = new ArrayDeque<>();
        queue.offer(new TreeNode[] {p, q});
        while (!queue.isEmpty()) {
            TreeNode[] pair = queue.poll();
            TreeNode a = pair[0], b = pair[1];
            // Two empty positions match; move on
            if (a == null && b == null) {
                continue;
            }
            // Missing node on one side, or different values
            if (a == null || b == null || a.val != b.val) {
                return false;
            }
            // Compare the children position by position later
            queue.offer(new TreeNode[] {a.left, b.left});
            queue.offer(new TreeNode[] {a.right, b.right});
        }
        return true;
    }
}

Go:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    queue := [][2]*TreeNode{{p, q}}
    for len(queue) > 0 {
        a, b := queue[0][0], queue[0][1]
        queue = queue[1:]
        // Two empty positions match; move on
        if a == nil && b == nil {
            continue
        }
        // Missing node on one side, or different values
        if a == nil || b == nil || a.Val != b.Val {
            return false
        }
        // Compare the children position by position later
        queue = append(queue, [2]*TreeNode{a.Left, b.Left}, [2]*TreeNode{a.Right, b.Right})
    }
    return true
}

JavaScript:

/**
 * 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) {
    const queue = [[p, q]];
    // Read with a moving head index: Array.shift() is O(n)
    for (let head = 0; head < queue.length; head++) {
        const [a, b] = queue[head];
        // Two empty positions match; move on
        if (a === null && b === null) {
            continue;
        }
        // Missing node on one side, or different values
        if (a === null || b === null || a.val !== b.val) {
            return false;
        }
        // Compare the children position by position later
        queue.push([a.left, b.left], [a.right, b.right]);
    }
    return true;
};

C#:

/**
 * 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;
 *     }
 * }
 */
using System.Collections.Generic;

public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        var queue = new Queue<(TreeNode, TreeNode)>();
        queue.Enqueue((p, q));
        while (queue.Count > 0) {
            var (a, b) = queue.Dequeue();
            // Two empty positions match; move on
            if (a == null && b == null) {
                continue;
            }
            // Missing node on one side, or different values
            if (a == null || b == null || a.val != b.val) {
                return false;
            }
            // Compare the children position by position later
            queue.Enqueue((a.left, b.left));
            queue.Enqueue((a.right, b.right));
        }
        return true;
    }
}

C++:

/**
 * 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) {}
 * };
 */
#include <queue>
#include <utility>
using namespace std;

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<pair<TreeNode*, TreeNode*>> pending;
        pending.push({p, q});
        while (!pending.empty()) {
            auto [a, b] = pending.front();
            pending.pop();
            // Two empty positions match; move on
            if (a == nullptr && b == nullptr) {
                continue;
            }
            // Missing node on one side, or different values
            if (a == nullptr || b == nullptr || a->val != b->val) {
                return false;
            }
            // Compare the children position by position later
            pending.push({a->left, b->left});
            pending.push({a->right, b->right});
        }
        return true;
    }
};

Complexity Analysis

  • Time: O(n), where n is the number of nodes in the smaller tree. Each pair is dequeued once, and pairs are only queued below nodes that matched.
  • Space: O(w), where w is the largest number of pairs waiting at once. For BFS that is about the widest level of the smaller tree, up to O(n) for a complete tree. Pick the recursive version when trees are deep and balanced, and this one when recursion depth is a concern.

Key Insights

  • Shape and values both matter. Comparing one traversal of the values is not enough: [4,7] and [4,null,7] both have preorder 4, 7. Compare nodes in matching positions instead.
  • Handle the null cases before reading values. Checking “both null” first, then “one null”, makes the value comparison safe.
  • The recursion mirrors the definition. Root equal, left subtrees equal, right subtrees equal. Writing the definition in words first makes the code obvious.
  • Early exit. Both versions stop at the first mismatch, so different trees are often rejected after a few nodes.
  • This is a building block. Subtree of Another Tree calls exactly this function at every node, and Symmetric Tree is the same walk with the left and right children crossed.

Edge Cases

  1. Both trees empty: return true.
  2. One tree empty, the other not: return false.
  3. Same values, different shape, like [4,7] versus [4,null,7]: return false.
  4. Same shape, one value different deep in the tree: must still be found, so the walk cannot stop early on success.
  5. Negative values and duplicates: compared like any other values; duplicates do not cause false matches because positions are compared, not values alone.
  6. A single node in each tree: true exactly when the values are equal.

Common Mistakes

  1. Reading p.val before checking for null. This crashes when only one tree has a node at that position.
  2. Returning true when only one side is null. One null means the shapes differ.
  3. Comparing a single traversal. Different trees can produce the same preorder, inorder or level-order sequence of values unless nulls are recorded too.
  4. Comparing node references (p == q) instead of values. The trees are separate objects; only their contents should be compared.
  5. Using a container that rejects nulls. Java’s ArrayDeque throws on null, which is why the iterative Java version wraps each pair in an array.

Interview Tips

  1. Say the recursive definition aloud first; the code is then a direct transcription.
  2. List the three base cases (both null, one null, values differ) before writing the recursive call.
  3. Offer the iterative version if asked about deep trees, and note that a stack or queue of pairs both work.
  4. State complexity in terms of the smaller tree, since the walk stops as soon as the trees diverge.
  5. Expect a follow-up such as Subtree of Another Tree or Symmetric Tree, which reuse this function.

Follow-up Questions

  1. Is one tree a subtree of the other? Run this check from every node of the larger tree, or serialize both and search. See Subtree of Another Tree below.
  2. Is a tree a mirror image of itself? Compare left with right and right with left. See Symmetric Tree.
  3. Are two trees the same after any number of child swaps? At each node, accept either the straight or the crossed pairing of children (LeetCode 951, Flip Equivalent Binary Trees).
  4. How would you compare many trees quickly? Serialize each tree (with null markers) or compute a structural hash per tree, then compare the strings or hashes.
  5. What if the trees were very deep? Use the iterative version so the call stack cannot overflow.