Start learning free

LESSON 418 OF 540 · BINARY TREES

Same Tree in Scala: Comparing Two Trees with Recursion in O(n)

Practice O(n) Read the full explanation

Given the roots of two binary trees, p and q, return true if they are the same tree, and false otherwise.

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

The trees below are written in level order (top to bottom, left to right), with null for a missing child.

Example 1:

     p          q
     1          1
    / \        / \
   2   3      2   3

Input: p = [1,2,3], q = [1,2,3]
Output: true
Explanation: Both trees have the root 1, with 2 as its left child and 3 as its right child.

Example 2:

     p          q
     1          1
    /            \
   2              2

Input: p = [1,2], q = [1,null,2]
Output: false
Explanation: The trees hold the same values, but the 2 is the left child of the root in p and the right child in q.

Example 3:

     p          q
     1          1
    / \        / \
   2   1      1   2

Input: p = [1,2,1], q = [1,1,2]
Output: false
Explanation: The shapes match, but the left children hold different values: 2 in p and 1 in q.

Constraints:

The number of nodes in each tree is in the range [0, 10⁴].
Each node value is between -10⁴ and 10⁴.
Each tree is at most 400 levels deep.

Note:

Your algorithm should run in O(n) time, where n is the number of nodes, comparing each pair of nodes at most once.

STEP 1 OF 4

Guided

Ctrl + Enter to check

SCALA · BINARY TREES

Same Tree in Scala, explained

Problem overview

The method isSameTree gets the roots of two binary trees, p and q, and returns true when they are the same tree. Two trees are the same when they have exactly the same shape and every node holds the same value as the node in the same place in the other tree. Two empty trees are the same. The lesson provides the TreeNode class, with an Int field value and the fields left and right, which are null for a missing child.

The trees [1, 2, 3] and [1, 2, 3] are the same. The trees [1, 2] and [1, null, 2] hold the same values, but the 2 is a left child in the first tree and a right child in the second, so the answer is false. The trees [1, 2, 1] and [1, 1, 2] have the same shape, but their left children hold 2 and 1, so the answer is false again.

Approach: compare the roots, then the subtrees

A tree is built from a root and two smaller trees, so equality has the same structure. Two trees are the same exactly when:

their roots are both missing, or both present with the same value, and
their left subtrees are the same, and
their right subtrees are the same.

Each of the last two conditions is the original question asked about smaller trees, so the method can call itself. The recursion ends at empty trees, which are the same as each other.

When the two roots are looked at, there are four cases, and the order of the checks decides which ones are safe:

Both are null: the trees are the same.
Exactly one is null: the shapes differ, so they are different.
Both exist but hold different values: different.
Both exist with equal values: the answer depends on the subtrees.

Testing "both null" first means that when the second check runs, at least one is non-null, and so "one of them is null" really means exactly one. Reading p.value is only safe after both checks have passed.

The method compares each pair of nodes at most once, so the time is O(n), where n is the number of nodes in the smaller tree.

Step by step

Both empty: if p == null && q == null, return true. This is the base case, reached whenever both trees step past a leaf together.
Only one empty: if p == null || q == null, return false. The first check already handled the case where both are missing, so this one has exactly one missing tree and one that isn't: the shapes differ.
Different values: if p.value != q.value, return false. Both nodes exist at this point, so reading their values is safe.
Compare the subtrees: return isSameTree(p.left, q.left) && isSameTree(p.right, q.right). The roots match, so the trees are the same exactly when both pairs of subtrees are.

The solution in Scala

class Solution {
    def isSameTree(p: TreeNode, q: TreeNode): Boolean = {
        if (p == null && q == null) {
            return true
        }
        if (p == null || q == null) {
            return false
        }
        if (p.value != q.value) {
            return false
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }
}

The Scala details worth noticing:

&& and || short-circuit. In p == null || q == null, the second test is skipped when p is null. In the last line, if the left subtrees differ, the right ones aren't compared at all.
== against null. For a class like TreeNode, p == null checks whether the reference is missing. == on two TreeNode objects would not compare their contents, because the class doesn't define equality, so the method compares the values and the children itself.
!= on Int values compares the numbers, as you would expect.
The result of a recursive call is a plain Boolean, so combining two calls with && is ordinary logic. A recursive def needs its return type written out, and Boolean is already in the signature.
The same object on both sides. isSameTree(a, a) returns true by walking the whole tree: the method never shortcuts on identity.

Complexity

Time: O(n), where n is the number of nodes in the smaller of the two trees. Each call compares one pair of nodes, and the recursion goes down only while the pairs match. At the first difference, the && chain stops.

Space: O(h) for the call stack, where h is the height of the trees. It is at most 400 here, and about log n for balanced trees.

Edge cases and common mistakes

Two empty trees. isSameTree(null, null) returns true.
One empty tree. null against a tree with one node returns false, in either order. The second check covers both orders, which is why it uses ||.
Same values, different shape. [1, 2] and [1, null, 2] return false. Comparing the lists of values alone would call them equal.
Same shape, different values. [1, 2, 1] and [1, 1, 2] return false: the multiset of values is equal, but the places differ.
Reading a value too early. Writing p.value != q.value before the null checks fails with a NullPointerException when one of the nodes is missing.
Zero values. Two single-node trees holding 0 return true. A node's value is never confused with a missing node, because missing nodes are null and not 0.
Using || to combine the subtree results. It would call the trees the same when only one side matches.

Testing

[1, 2, 3] and [1, 2, 3] gives true.
[1, 2] and [1, null, 2] gives false.
[1, 2, 1] and [1, 1, 2] gives false.
Two empty trees give true.
An empty tree and [1] give false, and so do [1] and an empty tree.
[0] and [0] gives true.
A tree compared with itself gives true.

Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free