← Algorithmic Patterns
easyTrees

Same Tree

Determine whether two binary trees have identical structure and equal values at corresponding nodes.

LeetCode ↗

Work through the cases

3 examples

Input notation

Two trees on separate lines, each using level order with null for missing children.

Expected result

true or false.
Case 1

Input

1 2 3
1 2 3

Expected output

true
Case 2

Input

1 2
1 null 2

Expected output

false
Case 3

Input

null
null

Expected output

true

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Whether two trees are the same depends on matching structure and values at every corresponding position. Collecting both traversals and comparing sequences still needs a sentinel encoding for missing children. n ≤ 100, so recursion is fine. A tree is defined by its root and two subtrees, so we only compare the current pair: both null means equal; one null or unequal values means not; otherwise recurse on the left children and the right children.

We can use the DFS recursive method to solve this problem.

First, determine whether the root nodes of the two binary trees are the same. If both root nodes are null, then the two binary trees are the same. If only one of the root nodes is null, then the two binary trees are definitely different. If both root nodes are not null, then determine whether their values are the same. If they are not the same, then the two binary trees are definitely different. If they are the same, then determine whether the left subtrees of the two binary trees are the same and whether the right subtrees are the same. The two binary trees are the same only when all the above conditions are met.

The time complexity is O(\min(m, n)), and the space complexity is O(\min(m, n)). Here, m and n are the number of nodes in the two binary trees, respectively. The space complexity mainly depends on the number of layers of recursive calls, which will not exceed the number of nodes in the smaller binary tree.

/**
 * 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 (p == q) return true;
        if (p == null || q == null || p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.