Start learning free

LESSON 419 OF 541 · BINARY TREES

Same Tree in Swift: Recursive Comparison 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 nil 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,nil,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

SWIFT · BINARY TREES

Same Tree in Swift, explained

Problem overview

The method isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool receives the roots of two binary trees and returns true when they are the same: the same shape, and the same value in every position. Two empty trees are the same. The lesson provides the TreeNode class, with val, left and right, and a missing tree or child is nil.

The trees [1, 2, 3] and [1, 2, 3] are the same. The trees [1, 2] and [1, nil, 2] hold the same values but are different: the 2 is a left child in the first and a right child in the second. The trees [1, 2, 1] and [1, 1, 2] have the same shape, but their left children hold 2 and 1.

Approach: compare the roots, then both pairs of subtrees

Two trees are the same when their roots hold the same value, their left subtrees are the same, and their right subtrees are the same. That is a definition you can code directly as recursion: the answer for a pair of trees depends on the answers for two smaller pairs.

Each call has three situations:

Both trees are empty: they are the same, and the recursion ends.
Exactly one is empty: the shapes differ, so the answer is false.
Both have a node: if the values differ, false. If they match, the trees are the same exactly when the left pair and the right pair are.

Every call compares one pair of nodes, and no pair is compared twice, so the time is O(n).

Step by step

Handle two empty trees first: if p == nil && q == nil, return true. This is also where the recursion stops when both sides step past a leaf at once.
Unwrap both at once: guard let p = p, let q = q else { return false }. The else branch runs when at least one is nil. Both being empty was handled above, so exactly one is empty and the shapes differ.
Compare the values: if p.val != q.val, return false. Both nodes exist here, so reading their values is safe.
Recurse on both pairs: isSameTree(p.left, q.left) && isSameTree(p.right, q.right).

The solution in Swift

class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p == nil && q == nil {
            return true
        }
        guard let p = p, let q = q else {
            return false
        }
        if p.val != q.val {
            return false
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }
}

The Swift details worth a closer look:

p == nil without Equatable. TreeNode is a class with no equality defined, but Swift lets you compare any optional with nil using == and !=. It asks only whether the optional is empty.
guard let p = p, let q = q unwraps two optionals in one statement. If either is nil, the else block runs. Below the guard, p and q are plain TreeNode values that hide the parameters of the same names. The else block must leave the function, here with return false.
Short-circuit &&. When the left pair is different, the right pair isn't examined.
Comparing values, not references. The code reads val, so two separate trees with equal contents are the same. A tree compared with itself, passed as both p and q, is also the same.

Complexity

Time: O(n), where n is the number of nodes in the smaller of the trees, at most, since the recursion ends as soon as the shapes differ. Each pair of nodes is compared once.

Space: O(h), where h is the height: the recursion goes one level deeper per node on the current path. The trees are at most 400 levels deep.

Edge cases and common mistakes

Both empty. [] and [] give true.
One empty. [] and [1] give false.
Same values, different shape. [1, 2] against [1, nil, 2] gives false: a check that compares only values in order would accept it.
A longer tree. [1, 2] against [1, 2, 3] gives false: the second tree has a right child the first lacks.
Reading .val before checking for nil. Accessing a value through a missing node would crash, which is why the order of the checks matters.
Value 0. [0] against [0] gives true: a value of zero is not an empty node.

Testing

[1, 2, 3] and [1, 2, 3] give true.
[1, 2] and [1, nil, 2] give false.
[1, 2, 1] and [1, 1, 2] give false.
[] and [] give true.
[] and [1] give false.
[1] and [1] give true.
[1, 2] and [1, 2, 3] give false.

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

Start learning free