Start learning free

LESSON 418 OF 540 · BINARY TREES

Same Tree in Kotlin: Comparing Two Trees with Recursion

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, 104].
  • Each node value is between -104 and 104.
  • 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
    Ctrl + Enter to check

    KOTLIN · BINARY TREES

    Same Tree in Kotlin, explained

    Problem overview

    The function isSameTree receives the roots of two binary trees, p and q, and returns true when they are the same tree: the same shape, with the same value in every place. Two empty trees are the same. The lesson provides the TreeNode class, with an Int field value and nullable left and right children, and the parameters have the type TreeNode? because a tree may be empty.

    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 are different: in the first, 2 is the left child of the root, and in the second it is the right child. The trees [1, 2, 1] and [1, 1, 2] have the same shape but different values in the left child.

    Approach: compare the roots, then the 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. A subtree is itself a tree, so this is a recursive definition, and the code follows it directly. Each call compares one node of p with the node in the same place of q.

    There are three ways for a pair of nodes to be decided without looking deeper:

    • both are missing: the trees agree here, so the answer is true;
    • exactly one is missing: the shapes differ, so the answer is false;
    • both exist but hold different values: the answer is false.

    If none of these applies, the answer depends on the two pairs of children. Every node of the smaller tree is compared at most once, so the time is O(n).

    Step by step

    1. Both empty. If p == null && q == null, return true. This is also the base case that ends the recursion when both trees step past a leaf together.
    2. Only one empty. If p == null || q == null, return false. The case of both being empty has already returned, so exactly one tree is missing a node here.
    3. Different values. If p.value != q.value, return false. Both nodes exist at this point, so reading their values is safe.
    4. Compare the children. Return isSameTree(p.left, q.left) && isSameTree(p.right, q.right). The roots already match, so the trees are the same exactly when both pairs of subtrees are.

    The solution in Kotlin

    class Solution {
    fun 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 Kotlin details worth a closer look:

    • Smart casts do the null checking. After if (p == null || q == null) return false, Kotlin knows that neither p nor q is null, so p.value and q.value compile without ?. or !!. Without that early return, the compiler would reject p.value.
    • The order of the checks matters. The "both null" test comes first. If the "one is null" test came first, two empty trees would be reported as different.
    • != compares values. In Kotlin, == and != call equals. For Int fields they compare the numbers. The identity operator is ===, which isn't needed here, since the trees are compared by content, not by whether they are the same object.
    • Short-circuit &&. When the left subtrees differ, the right subtrees are not examined.

    Complexity

    Time: O(n), where n is the number of nodes in the smaller tree. Each call compares one pair of positions, and the recursion stops as soon as a difference is found.

    Space: O(h), where h is the height of the trees, for the recursion stack. The trees are at most 400 levels deep.

    Edge cases and common mistakes

    • Two empty trees. [] and [] give true.
    • One empty tree. [] and [1] give false.
    • Same values, different shape. [1, 2] and [1, null, 2] give false. Comparing only the values of the nodes, in any traversal that skips missing children, can't tell them apart.
    • Same shape, different values. [1, 2, 1] and [1, 1, 2] give false.
    • One tree inside the other. [1] and [1, 2] give false: the second has an extra node, so at the left child one side is missing.
    • The same object twice. Passing one tree as both p and q gives true.
    • Swapping the checks. Testing p.value != q.value before the null checks fails to compile, because p and q may still be null there.

    Testing

    Trees are written in level order, with null for a missing child.

    • p = [1, 2, 3], q = [1, 2, 3] gives true.
    • p = [1, 2], q = [1, null, 2] gives false.
    • p = [1, 2, 1], q = [1, 1, 2] gives false.
    • p = [], q = [] gives true.
    • p = [], q = [1] gives false.
    • p = [1], q = [1, 2] gives false.
    • p = [7], q = [7] gives true.
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free