Same Tree

EasyTree Binary Tree DFS Recursion

A compiler caches the machine code it generated for every expression tree it has already compiled. Before reusing a cached result, it must confirm that the new tree is identical to the cached one: the same shape, with equal values at every matching position.

Given the roots p and q of two binary trees, return true if they are identical and false otherwise. Two empty trees are identical.

Example 1

Input: p = [4,7,9,null,2], q = [4,7,9,null,2]
Output: true

Explanation: Same shape and the same value at every position.

Example 2

Input: p = [4,7,9], q = [4,9,7]
Output: false

Explanation: The values are the same, but the two children of the root are swapped.

Example 3

Input: p = [3,1,5], q = [3,1,5,null,null,4]
Output: false

Explanation: q has an extra node, 4, below the 5.

Constraints

Each tree has between 0 and 100 nodes.
Node values are integers from -10^4 to 10^4.

💡 Hint 1

Compare the two roots first. What must be true about them before looking deeper?

💡 Hint 2

If both nodes are null the trees match here; if exactly one is null they do not. Otherwise the values must be equal and both pairs of children must match recursively.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Walk both trees in lockstep. At each pair of positions: if both nodes are null this branch matches; if only one is null, or the values differ, the trees differ. Otherwise recurse on the two left children and the two right children, and require both to match. The && short-circuits, so the walk stops at the first difference.

Time O(min(n, m))Space O(min(h1, h2)) recursion depth

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

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

/**
 * Definition for a binary tree node (provided):
 * function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
 *
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
function isSameTree(p, q) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit