Same Tree

The problem

You are given the roots of two binary trees, first_tree and second_tree. Return true if they are the same tree, and false if not.

Two trees are the same when they have the same shape and every node holds the same value as the node in the same place in the other tree.

Trees in the examples are written level by level, from left to right. null marks a missing child.

Example 1

Input: first_tree = [6, 4, 9, 2, 5], second_tree = [6, 4, 9, 2, 5]

Output: true

Every node in first_tree has a partner in the same place in second_tree, with the same value.

Example 2

Input: first_tree = [3, 1], second_tree = [3, null, 1]

Output: false

The values are the same, but in first_tree the 1 is a left child and in second_tree it is a right child. The shapes differ.

Example 3

Input: first_tree = [8, 2, 7], second_tree = [8, 7, 2]

Output: false

The shapes match, but first_tree has 2 on the left and second_tree has 7 on the left.

Constraints

• Each tree has 0 to 100 nodes.
• -10,000 ≤ Node.val ≤ 10,000

Clarifying questions

Does the shape matter, or only the values?

Both. A left child and a right child with the same value are different.

Can one or both trees be empty?

Yes. Two empty trees are the same. An empty tree and a non-empty one are not.

Can values repeat inside a tree?

Yes. That is fine, because we compare nodes by place, not by searching for values.

Can we stop early?

Yes. The first difference decides the answer, so the rest of the trees need not be checked.

Spot the pattern

“Same tree” splits into smaller questions of the same kind: same root value, same left subtree, same right subtree. That is a tree traversal by recursion. The only twist is that it walks two trees at once, one pair of nodes per call.

Solutions

RecursionO(n)

Show all

There is only one approach worth showing. Any difference could hide in any node, so every pair must be checked, and this checks each pair once.

Recursion O(n)

The idea

Compare the two roots first. There are three cases.

• Both are empty. They match, so return true.
• One is empty and the other is not, or the values differ. They do not match, so return false.
• Both exist with the same value. Then the trees are the same only if the two left subtrees are the same and the two right subtrees are the same. Ask both questions with the same function.

The and stops early. If the left pair already failed, the right pair is never checked.

Why it is correct: two trees are the same exactly when the roots match and both pairs of subtrees are the same. The function checks exactly that, at every pair of nodes, down to the empty spots.

Walkthrough

call stack (first_tree, second_tree) top →

empty

1. def same(first_tree, second_tree):
2. if first_tree is None and second_tree is None:
3. return True
4. if first_tree is None or second_tree is None or first_tree.val != second_tree.val:
5. return False
6. return (same(first_tree.left, second_tree.left)
7. and same(first_tree.right, second_tree.right))

first_tree is on the left and second_tree is on the right. Walk both at the same time, one pair of nodes per call.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Recursion: two trees are the same when their roots match and both
    // pairs of subtrees are the same. Each node pair is checked once.
    public boolean isSameTree(TreeNode firstTree, TreeNode secondTree) {
        // Two empty spots match.
        if (firstTree == null && secondTree == null) return true;
        // One empty and one not is a shape difference. Different values
        // are a value difference. Either one ends the check.
        if (firstTree == null || secondTree == null || firstTree.val != secondTree.val)
            return false;
        // The roots match, so the answer depends on both sides.
        return isSameTree(firstTree.left, secondTree.left)
            && isSameTree(firstTree.right, secondTree.right);
    }
}

Big O

Time O(n)Space O(h)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There is no loop. The work repeats through recursion, so we count the calls. Each call does a fixed job: a few checks for empty, one value compare and at most two more calls. So each call counts as 1 step.

   1. def same(first_tree, second_tree):
   2. if first_tree is None and second_tree is None:
   3. return True
   4. if first_tree is None or second_tree is None or first_tree.val != second_tree.val:
   5. return False
   6. return (same(first_tree.left, second_tree.left)
   7. and same(first_tree.right, second_tree.right))

2. 2 Count the runs on Example 1

   In Example 1 both trees have 5 nodes, and they match everywhere. So each of the 5 pairs of nodes gets one call. The 3 leaves of first_tree each have 2 empty children, which makes 6 pairs of empty spots. Each of those gets a call that returns true at once.

   5 node calls + 6 empty calls = 11 calls.

   total calls

   5 node pairs + 6 empty pairs = 11

3. 3 Write the count for any n

   Let n be the number of nodes in the smaller tree. The walk stops at the first difference, so the worst case is two equal trees with n nodes each. Then each pair of nodes gets one call, and each of the n + 1 pairs of empty spots gets one call.

   n + (n + 1) = 2n + 1 calls

   Check it with Example 1: 2 × 5 + 1 = 11.

4. 4 Keep only the part that grows fastest

   • Drop the + 1. One call more does not change the growth.
   • Drop the 2. When n doubles, 2n doubles too.

   What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code creates no list or map. But calls that have started and not returned wait on the call stack, the memory a program keeps for unfinished calls. At most h of them wait at once, where h is the height of the trees: the number of levels on the longest path down.

   In Example 1, h is 3. A balanced tree has h about log n, but a chain has h = n. So the space is O(h), and O(n) in the worst case.

   call stack (one frame per level)

Common mistake

Comparing only the values in order

Walking each tree in the same order and comparing the lists of values is not enough. [3, 1] and [3, null, 1] give the same pre-order list, 3 then 1, but the shapes differ. Either compare node by node, as here, or put a marker for every empty spot into the lists.

Tested at the limits

2,000 random pairs of trees of 0 to 8 nodes: exact copies, copies with one value changed, and trees of other shapes. The recursion gave the same answer every time as a simple check that compares the two trees level by level.

Largest inputs	Result
Two identical trees of 100 nodes (the most allowed), balanced. Recursion.	Under 0.001 s, and under 0.01 MB of extra memory. Identical trees are the slowest case, because every pair of nodes is compared.
Two identical lines of 100 nodes. Recursion.	Under 0.001 s, and about 0.01 MB of extra memory: 100 calls wait at once, one per level, which is the O(h) space.